http://demos.thejit.org/example/rgraph/example1/
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.
http://packages.ubuntu.com/
The Ubuntu package list. One can find .debs to download here.
http://www.debian.org/doc/manuals/apt-howto/ch-search.en.html
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.