Have you simply tried to compile the PerlMagick package? If you got a prebuilt distribution, chances are that the libraries you should provide the path for are those which already populate INC and LIBS - so you have to do nothing.

If you encounter problems, look for the ImageMagick stuff (libraries in "lib" directories, header files in "include" directories), probably under /usr or /usr/local. I would also suggest to look at the "pre-built binary" (is it a tgz file?), usually source distributions tend to put things into /usr/local by default, while compiled packages have a bias for /usr.