[I'm writing a new answer for the perlfaq]
You can use the ExtUtils::Installed module to show all installed distributions, although it can take awhile to do its magic. The standard library which comes with Perl just shows up as "Perl" (although you can get those with Mod::CoreList).
my $inst = ExtUtils::Installed->new();
my @modules = $inst->modules();
If you want a list of all of the Perl module filenames, you can use File::Find::Rule.
my @files = File::Find::Rule->file()->name( '*.pm' )->in( @INC );
If you simply need to quickly check to see if a module is available, you can check for its documentation. If you can read the documentation the module is most likely installed. If you cannot read the documentation, the module might not have any (in rare cases).
prompt% perldoc Module::Name