Presumes a 1-to-1 mapping between .pm and package (i.e. this won't always work, but then again neither will your search).

pmpath () { perl -le "eval { require ${1} }; if( \$@ =~ /locate (\S+)\
+.pm/ ) { print qq{${1} not installed}; exit 1; }(\$m=qq{${1}.pm})=~s{
+::}{/}g;print qq{${1}: }, \$INC{\$m}" }

$ pmpath CGI
CGI: /usr/lib/perl5/5.8.0/CGI.pm
$ pmpath POE::Wheel::Run
POE::Wheel::Run: /usr/lib/perl5/site_perl/5.8.0/POE/Wheel/Run.pm
[download]