Hmmm, you might want to check out par.

#> pp -o packed.exe source.pl        
# creates a self-contained binary.

Modules can reside in different directories in a PAR file:

        /                       # casual packaging only
        /lib/                   # standard location
        /arch/                  # for creating from blib/ 
        /i386-freebsd/          # i.e. $Config{archname}
        
Par was tested on Win32, FreeBSD, Linux, AIX, Solaris with Perl 5.6.1 
+and 5.8.0.
[download]

It has truckloads of more options according to these pages, you might want to check out the newest version of par anyway, since it seems to do everything perl2exe does (even more I think).

Oh, and did I mention it was free (unlike perl2exe)?

Teabag
Sure there's more than one way, but one just needs one anyway - Teabag