Ubuntu/Debian: Show list of available versions of a specific package

Try with

apt-cache madison myPackage

Quote from man page:

It displays available versions of a package in a tabular format.

apt-cache policy myPackage

If you like to know which package versions are included into some particular Debian/Ubuntu/Backports release, rmadison tool from devscripts package could be the answer. For example:

$ rmadison -u debian,ubuntu,bpo mercurial | cut -d "|" -f 1-3
debian:
 mercurial | 0.9.1-1+etch1 |     etch-m68k 
 mercurial | 0.9.1-1+etch1 |     oldstable 
 mercurial |  1.0.1-5.1 |        stable 
 mercurial |    1.5.1-2 |       testing 
 mercurial |    1.5.2-1 |      unstable 
ubuntu:
 mercurial |      0.7-8 | dapper/universe 
 mercurial |    0.9.5-3 | hardy/universe 
 mercurial | 1.0.1-5.1~hardy1 | hardy-backports/universe 
 mercurial | 1.1.2-2ubuntu1 | jaunty/universe 
 mercurial |    1.3.1-1 | karmic/universe 
 mercurial |    1.4.3-1 | lucid/universe 
 mercurial |    1.5.2-1 | maverick/universe 
bpo:
 mercurial | 1.0.1-5.1~bpo40+1 | etch-backports 
 mercurial | 1.3.1-1~bpo50+2 | lenny-backports 

It will show "official" information, regardless of repositories you have configured on your system.

Please note, that versions between releases are not kept as a part of official repositories. However, you can give a shot to recently launched http://snapshot.debian.org service, which allows to access to old packages based on dates and version numbers uploaded to Debian archive since around 2005.

Similar tool you may be interested in is whohas, which goes far beyond Debian family. It's able to show versions of available software for other distributions (Arch, openSUSE, Gentoo, FreeBSD and even more - 14 distros at the moment).

Hope that helps.

As @Ilya pointed out you can use whohas:

whohas -d Debian,Ubuntu package | tr -s ' ' '\t' | cut -f 1-3 | column -t