A really cool deb / apt package dependency visualiser. It's a demo, but can be used by running "PageController.makeRequestAndPlot('PackageName');" in a firebug console.
The Ubuntu package list. One can find .debs to download here.
Handy howto from the debian manual on browsing packages with apt. Includes explanations of the most common operations (apt-cache search, etc) and what they do.