debian/ubuntuでCPANのモジュールをaptでいれるには、以下の命名規則で探すと良いでしょう。
lib<パッケージ名(::は-に置き換え)>-perl
たとえばArchive::Zipの場合、libarchibe-zip-perlとなります。
……ということを知らずに、apt-get install perl-で補完をかけても何もない思っていた（そもそもapt-cache searchを使って探せよというツッコミもある）ので、だいぶ遠回りをしてしまいました。CPANにあるモジュールをdebianパッケージにできるツールを見つけて作ろうとしたら「そのパッケージもうaptにあるで」と言われて気づきました。
CPANにあるモジュールをdebianパッケージにできるツールはこちらを参照。いよいよaptにもないパッケージを作りたいときはこれを使えば良いようです。
http://www.debian-administration.org/article/78/Building_Debian_packages_of_Perl_modules
