As much criticism as it often gets, I personally have found the
Slash code to be a good example, particularly in this area.

Slashcode has to download required modules, create directories,
modify permissions, creates DB tables, and I believe it may even change a config script somewhere,
but don't quote me on that.

In the root directory of the distribution, they have a typical
Makefile that you might see in say, a C program. It begins copying some
files into place, modifying permissions, and that sort of thing.
But then it recurses through all the Perl directories, and runs the Makefile.PL
files in those directories, which each use ExtUtils::MakeMaker.

I don't remember how slash does it, but MakeMaker is often what is used to
create dependencies for your application. If it doesn't do what
you need, you can also use the CPAN module and just do something like:

use CPAN;
my @required_modules = qw(CGI XML::Parser HTML::Template);
foreach my $module ( @required_modules ) {
   print "Checking for $module";
   eval "require $module";
   if($@) {
      print "failed\n";
      print "$module does not seem to be present!  I'll install it now
+.\n";
      CPAN::Shell->install($module);
   }  
}
[download]

You can just put those lines in your Makefile.PL. HTH
-Eric