If you are on Unix, then use /bin/which:

~/> /bin/which perl

/usr/local/bin/perl
[download]

But I would write a little shell wrapper that checks for the existance of Perl interpreter (instead of doing it in perl).

If you are on Windows, then you could write a little stub that checks for the Windows REGKEY - "My Computer\HKEY_CLASSES_ROOT\Applications\perl.exe\shell\Open\command\(Default)" for the path to Perl executable.

You can also ask the user if they have Perl installed during the installation process.

Somehow I am puzzled why do you need to have Perl installed anyway if you decide to 'pre-compile' your Perl script(s) into a single executable. Doesn't the Perl packager you use to create standalone executables already comes with a full perl interpreter?