I've had this problem myself.  Devel::Modlist (as suggested by this answer) takes a dynamic approach.  It reports the modules that were actually loaded during a particular run of your script.  This catches modules that are loaded by any means, but it may not catch conditional requirements.  That is, if you have code like this:
if ($some_condition) { require Some::Module }
and $some_condition happens to be false, Devel::Modlist will not list Some::Module as a requirement.
I decided to use Module::ExtractUse instead.  It does a static analysis, which means that it will always catch Some::Module in the above example.  On the other hand, it can't do anything about code like:
my $module = "Other::Module";
eval "use $module;";
Of course, you could use both approaches and then combine the two lists.
Anyway, here's the solution I came up with:
#! /usr/bin/perl
#---------------------------------------------------------------------
# Copyright 2008 Christopher J. Madsen <perl at cjmweb.net>
#
# This program is free software; you can redistribute it and/or modify
# it under the same terms as Perl itself.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See either the
# GNU General Public License or the Artistic License for more details.
#
# Recursively collect dependencies of Perl scripts
#---------------------------------------------------------------------
use strict;
use warnings;
use File::Spec ();
use Module::CoreList ();
use Module::ExtractUse ();
my %need;
my $core = $Module::CoreList::version{'5.008'};
# These modules have lots of dependencies.  I don't need to see them now.
my %noRecurse = map { $_ => 1 } qw(
  Log::Log4perl
  XML::Twig
);
foreach my $file (@ARGV) {
  findDeps($file);
}
foreach my $module (sort keys %need) {
  print "  $module\n";
}
#---------------------------------------------------------------------
sub findDeps
{
  my ($file) = @_;
  my $p = Module::ExtractUse->new;
  $p->extract_use($file);
  foreach my $module ($p->array) {
    next if exists $core->{$module};
    next if $module =~ /^5[._\d]+/; # Ignore "use MIN-PERL-VERSION"
    next if $module =~ /\$/;        # Run-time specified module
    if (++$need{$module} == 1 and not $noRecurse{$module}) {
      my $path = findModule($module);
      if ($path) { findDeps($path) }
      else       { warn "WARNING: Can't find $module\n" }
    } # end if first use of $module
  } # end foreach $module used
} # end findDeps
#---------------------------------------------------------------------
sub findModule
{
  my ($module) = @_;
  $module =~ s!::|\'!/!g;
  $module .= '.pm';
  foreach my $dir (@INC) {
    my $path = File::Spec->catfile($dir, $module);
    return $path if -f $path;
  }
  return;
} # end findModule
You'd run this like:
perl finddeps.pl scriptToCheck.pl otherScriptToCheck.pl
It prints a list of all non-core modules necessary to run the scripts listed.  (Unless they do fancy tricks with module loading that prevent Module::ExtractUse from seeing them.)