The general strategy would be to compile Perl on a machine that's compatible with the target systems, and install it into the appropriate directory, i.e. the one that you want to have it installed on the target systems. This is because a Perl 5.8 installation is not 'relocatable' (as opposed to 5.10) — the installation path is hardcoded in the binary, so it will find its libs via the default @INC. Also, it's probably easiest to use a directory layout where everything (binary, libs (modules), docs) is below one toplevel directory. See the INSTALL file that comes with the source for the details.

Then, create a tarball (or whatever package format you're using for your app) of the entire directory tree into which you've installed Perl, and bundle that with your application. That's it, essentially.