I don't bother checking in my modules, but it's reasonable to check in your Makefile.PL so they know when installing it (or CPAN.pm knows) that they need something else. I even check for standard modules. If you use ExtUtils::MakeMaker, just add a PREREQ_PM hash arg to the arguments to WriteMakefile. From Archive-Zip's Makefile.PL:

WriteMakefile(
#snip
 PREREQ_PM  => {
  'Compress::Zlib'    => 1.06,
  'Carp'       => 0,
  'File::Path'     => 0,
  'File::Find'        => 0,
  'File::Basename' => 0,
 },
#snip
);
[download]

If you have PREREQ_PM set, CPAN.pm will use it to load prerequisites. Also, the .PPD file (used by PPM) will have the dependency information, which will allow PPM to load the required modules.

update: added explanation at end