Check out PerlApp from ActiveState, http://www.activestate.com/. It packs the Perl binaries, script source, and all required modules into a single executable. I think there is a Linux version but it is most useful for Windows.
Also look at Perl2Exe, http://www.indigostar.com/perl2exe.htm.