How do I pass the hint to gcc about where to find MagickCore.h?
Add to %PATH% so the .dll's can be found
cpanp -z Image::Magick
perl Makefile.PL LIBS="-Lpath\to\directory -llibname -libname... " INC="-Ipath/to/includes -Ipath/to/other/includes"
If your Makefile.PL is being too clever, you should edit Makefile.PL and prefix :nosearch
For microsoft you could set (like PATH) env vars INCLUDE= for .h-headers and LIB= for .lib's -- I can't remember if mingw/gcc also respects this, so if it doesn't, you'd set C_INCLUDE_PATH/LIBRARY_PATH, see http://gcc.gnu.org/onlinedocs/gcc/Environment-Variables.html