Debian and Ubuntu come with a lot of modules from CPAN packaged for the distro.

The naming convention is: convert :: to -, make all the letters lowercase, and add lib to the beginning and -perl to the end. For example: POE::Component::IRC is packaged as libpoe-component-irc-perl.

I've also had limited success with dh-make-perl which fetches from CPAN and builds debs. You often have to manually specify depends and build-deps, which can be tedious and error-prone.