rmadison is part of the devscripts package. It's a fantastic little tool that tells you which version of a package is in which release of Ubuntu or Debian. It's also the quickest way to see if a package is in one of them at all - very handy to check package requests on Launchpad and in Brainstorm.
apt-cache is part of the default Ubuntu install. It's very handy to find the right package name, dependencies, and other clues when tracking down the correct package for Launchpad or Brainstorm.
Cool! Package apt-rdepends installs a shell command (also apt-rdepends) that gives a clean list of all dependencies. Reverse searching is also possible. I needed something like this in Iraq, when I was upgrading by hand due to a lack of internet connection for my laptop.
Interestingly, Synaptic has grown a script-maker for offline package changes. It generates a script that you use on a connected machine to download the right packages. I could have used that, too...
Now they are merely of academic interest - unless I go back.
Instead of using the apt-rdepends package, you can get the same result using the apt-cache rdepends packagename command.
