To make the Debian-Perl module look-up more useful, there are now install instructions included. That means that all non-packaged CPAN dependencies and also all packaged ones are listed and it's clear what can be installed from packages and what needs to be installed from CPAN. Here's an example for App::TimeTracker:
sudo apt-get install libexception-class-perl libclass-accessor-perl libmoosex-role-parameterized-perl libjson-perl libnamespace-autoclean-perl libtry-tiny-perl libtest-trap-perl libtest-most-perl libtest-file-perl librt-client-rest-perl libpath-class-perl libmoosex-types-path-class-perl libmoosex-storage-perl libmoosex-getopt-perl libmoose-perl libmodule-build-perl libtest-mock-lwp-perl libjson-xs-perl libio-capture-perl libhash-merge-perl libgit-repository-perl libfile-homedir-perl libfile-find-rule-perl r-base-core-ra perl-modules libdigest-sha1-perl libdatetime-format-iso8601-perl libdatetime-format-duration-perl libdatetime-perl perl perl-base
sudo cpan -i Iterator Path::Class::Iterator MooseX::Storage::Format::JSONpm App::TimeTracker
Just a note that this works fine for Debian stable+testing+unstable. Which is not so common. Most installations will be stable or testing+unstable. Once Debian Wheeze (7.0) will become stable (hopefully soon) I'll split that search to two - one for Debian stable and one for Debian testing+unstable.