Packages known by your system / offline
You can use apt-cache to query the APT cache. To show the versions known by your system use apt-cache policy. Example:
apt-cache policy iceweasel
iceweasel:
Installed: 10.0.4esr-3
Candidate: 10.0.4esr-3
Version table:
12.0-7 0
1 http://ftp.us.debian.org/debian/ experimental/main amd64 Packages
*** 10.0.4esr-3 0
500 http://ftp.us.debian.org/debian/ sid/main amd64 Packages
100 /var/lib/dpkg/status
10.0.4esr-2 0
500 http://ftp.us.debian.org/debian/ testing/main amd64 Packages
This means iceweasel version 12.0-7 is available in experimental and has priority 1, version 10.0.4esr-3 is installed from sid and has priority 500 and 10.0.4esr-2 is in testing.
For a detailed description about the meaning of priorities have a look at apt_preferences(5)
You can also display a brief description and some meta information about the package with
apt-cache show package-name
Information about all debian packages / online
If you want to get version information about all available debian packages (basically what http://packages.debian.org does) you can use rmadison(1) to remotely query the database. rmadison is in the devscripts package which you have to install via apt-get install devscripts.
$ rmadison iceweasel
iceweasel | 3.0.6-3 | lenny-security | source, alpha, amd64, arm, armel, hppa, i386, ia64, mips, mipsel, powerpc, s390, sparc
iceweasel | 3.0.6-3 | lenny | source, alpha, amd64, arm, armel, hppa, i386, ia64, mips, mipsel, powerpc, s390, sparc
iceweasel | 3.5.16-11~bpo50+1 | backports/lenny | source, alpha, amd64, armel, i386, ia64, mips, mipsel, powerpc, s390, sparc
iceweasel | 3.5.16-14 | squeeze | source, amd64, armel, i386, ia64, kfreebsd-amd64, kfreebsd-i386, mips, mipsel, powerpc, s390, sparc
iceweasel | 3.5.16-15 | squeeze-p-u | source, amd64, armel, i386, ia64, kfreebsd-amd64, kfreebsd-i386, mips, mipsel, powerpc, s390, sparc
iceweasel | 3.5.16-15 | squeeze-security | source, amd64, armel, i386, ia64, kfreebsd-amd64, kfreebsd-i386, mips, mipsel, powerpc, s390, sparc
iceweasel | 10.0.4esr-2~bpo60+1 | squeeze-backports | source, amd64, i386, kfreebsd-amd64, kfreebsd-i386, s390
iceweasel | 10.0.4esr-2 | wheezy | source, amd64, armel, armhf, i386, ia64, kfreebsd-amd64, kfreebsd-i386, mips, mipsel, powerpc, s390, s390x, sparc
iceweasel | 10.0.4esr-3 | sid | source, amd64, armel, armhf, hurd-i386, i386, ia64, kfreebsd-amd64, kfreebsd-i386, mips, mipsel, powerpc, s390, s390x, sparc
iceweasel | 11.0-4 | experimental | source, armel
iceweasel | 12.0-3 | experimental | source, mips
iceweasel | 12.0-7 | experimental | source, amd64, armhf, hurd-i386, i386, ia64, kfreebsd-amd64, kfreebsd-i386, powerpc, s390, s390x, sparc
The difference between apt-cache and rmadison is that apt-cache shows only the information known to your system (but can be used offline) while rmadison shows all version of available packages