If you're looking to conform to some standard way of doing this you may want to look at the FHS, which contains all the detail you could ever want on the subject.

Personally I'd say install your binaries in /usr/bin or /usr/local/bin, /bin is supposed to contain only essential binaries and should preferably not be cluttered by user applications (as a rule of thumb, /bin should contain only the binaries you need after a boot if you cannot mount anything except the root partition). perl isn't usually installed in /bin, and neither should your apps be.

As for the libraries, I usuall install somewhere in @INC. If your app will only be installed on a range of machines which belong to your organisation, then you could install in a custom directory and use lib, but I think it's too much of a bother to keep track of which apps need which library paths and only use this method when I'm testing a newer version of the libraries with an older one still installed. Also, installing libraries all over the filesystem can make it hard for someone else to maintain the system because they have to check all your custom paths as well as the usual ones for outdated library versions.

Another good thing to do is to convert your Perl tar.gz packages into the package format native to your platform( for example .rpm for Fedora) and install from there. This is trivially easy to do on .deb-based systems, due to the very useful dh-make-perl script, and I'd guess something similar is available for rpm as well (or you could always use dh-make-perl and then convert the resulting .deb into .rpm with alien). Sticking to the system packaging format makes it easier for an admin to know what version of what software is installed where, which application a particular file belongs to etc. It also simplifies installation and update for multiple machines.