All of PAR, PerlApp (which is part of the Perl Dev Kit) and perl2exe work very well.

All share the same problem of sometimes having trouble to determine what modules to package (solution: manually "use" the problematic modules in your script )

Start with PAR, it's free and most likely everything you need. Don't forget to put a nice icon on the binary. Non-geeks care for that.

/J