flycast: the apt-cache command can be used to search for available packages. With a little practise and creative use of grep, it's usually possible to narrow down results.
When I read your question, I used this command to search for the zlib perl module:
Code:
apt-cache search perl | grep -i zlib
..which returned a few results. Forgive me for not pasting them, I'm playing with debian via vmware and I didn't work out how to copy-paste between that and my main system.
This is my first port of call when trying to find a package which provides something I want.
Failing that, I might use the synaptic package manager to search. I prefer the command line tools because I find it faster to use them, but you should use whatever you're most comfortable with.