I'm on the XP half of my duel-boot now, so all this stuff is IIRC, but..

I think $^O eq 'Linux'.

The rule, according to the approps standard (part of the perl package, IIRC), is to take the name of the "primary package", s/::/-/g, tr/A-Z/a-z/, and lib$_-perl. IE Foo::Bar becomes libfoo-bar-perl. However, in pratice, the pratice is to take the name of the CPAN distribution, and not prepend lib if the distro already begins with lib. For example, Net::SNMP is part of the libnet CPAN distro, even though there is no package Net.pm.

One thing you could do if you want to figure out what debian package a given perl module maps on to is to do an apt-get search on the name of the module. That'll only work if the package description mentions the package. Another possiblity is to transform the package name into a filename (s|::|/|g, append .pm), and search Contents for that (either download Contents first, or use the web interface on packages.debian.org).