As I use Debian as my work desktop I quite often use
apt-cache search keyword | grep perl
as a first step when looking for Perl module for certain task. For those who are not familiar with Debian - apt-cache is just a tool to search for Debian packages by keywords. It actually works often quite well because if Perl package was repackaged as Debian package there is a very good change it is an old well proven module which is being used by many other people. Only if I don't like Debian package search results I go shopping on CPAN.
