bikeNomad mentioned PREREQ_PM, but nobody else mentioned h2xs, so I will. Read the perdocs on h2xs, create a skelton module with h2xs (probably with the -A and -X options), and edit it accordingly, like the PREREQ_PM in Makefile.PL. Also look at the perldocs at ExtUtils::MakeMaker (the EXE_FILES arrayref argument is probably what you want). Then look at what other people do in their modules. If the WriteMakefile in Makefile.PL fails, you could kick off the CPAN module to install the necessary modules.

Update: Hmm, WriteMakefile() warns you if modules in PREREQ_PM are not present, but it doesn't set any flag or return failure or anything. There's some commented out code in MakeMaker.pm that seems like there was some attempt to autoinstall via the CPAN module any missing modules, but I wonder why its not implemented. It would have been a nice option. You could still try to roll your own in the Makefile.PL, though.