The best and simplest and very traditional answer, is let the compiler do all the finding

You write the xs/c/cpp code that includes what headers iit needs, link the libs in Makefile.PL, and the compiler does the finding

If includes arent in default compiler findable directories, let the user add any extra directories, like he is supposed to

http://gcc.gnu.org/onlinedocs/gcc/Environment-Variables.html like C_INCLUDE_PATH/LIBRARY_PATH...