It'll depend on your target audience and the skill you perceive them to have. For many platforms, releasing your work to CPAN and directing your users there may do the trick. For the average IT department, it shouldn't be that hard to install Perl. For Joe User, I think the same applies, but of course I may well be mistaken.
The BSD systems come with ports or pkgsrc collections that are fairly kind to CPAN modules. An (arbitrary) example from OpenBSD: p5-AnyEvent for AnyEvent.
Using CPAN would also work for Mac OS X, I suppose. So long as you package a script that does the install for you. Such will probably require sudo/admin rights, but the GUI can handle that. I've seen such interaction used for e.g. printer driver installations.
For Windows, you could package the strawberry Perl MSI files along with a batch file to use CPAN for the install of your code. Obviously, there are cleaner ways, but I of course do not know how much you care to spend in resources.