Stuff under examples, eg, or ex directories are, IMO, partially meant for documentation to show how the module is used. Putting real codes (read: runnable examples) along with some description are best to put in the POD, be it in the main package or a package of its own.

But I assume that the examples are supposed to be runnable so they must be on their on files. If this is the case then it's actually natural to have these files are officially installed somewhere in the path. The problem is, the standard path installation of Perl modules are not like normal programs. For Linux system for example, there's a bunch of places to put different kind of stuff around.

My suggestion is to specify those examples files as executable files so the module installation process will put those files to the standard place, e.g. /usr/bin. To achieve this you say in the Makefile.PL file:

WriteMakefile(
  # other standard pairs
  EXE_FILES => [qw(
    examples/file1
    examples/file2
    examples/fileN
  )],
);
[download]

For other destination of where to install the examples, you may want to tweak the Makefile.PL based on ExtUtils::MakeMaker, or other means for module installation like Module::Build or Module::Install.

Yet, I don't guarantee this to be "intuitive" :-)