Read the docs for ExtUtils::MakeMaker. Your Makefile.PL should be written in terms of the PREFIX, INSTALLBIN, etc. macros. The user's perl and CPAN configuration will determine which directories are chosen for installation.

Many CPAN modules install executable scripts. For instance, LWP installs GET and HEAD utilities, among others.

I didn't mention Module::Build. I'm not too familiar with it and I'm not yet convinced that it's a good idea to reject make.