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.