How do I get a list of available (i.e. uninstalled) packages in Debian?

apt-cache is used for querying the package cache:

apt-cache pkgnames | sort

apt-cache search thing

apt-cache search --names-only thing

grep-dctrl and its derivatives provide a great way to query the apt cache files. (You can install these tools on ubuntu with sudo apt-get install dctrl-tools )

In the case of available (but not necessarily installed) packages, you can use grep-available. For example, to list all available packages:

grep-available  -s Package .

Edit:

aptitude can show you a list of Not Installed Packages by just launching it.

You can also get a list of not installed packages with aptitude by using:

aptitude -F "%p" search "?not(?installed)"

Note that with the new multi-arch packages, you'll get packages for other architectures listed in this result. For example, I get:

aptitude -F "%p" search "?not(?installed)"  | grep "^bash:"
bash:i386

I have the bash package installed, but it's the amd64 version, since my OS is installed with the amd64 version of Ubuntu Precise. If you don't want to see these packages for other architectures, you can exclude lines containing ::

aptitude -F "%p" search "?not(?installed)"  | grep -v ':'

Use apt-cache for this purpose:

apt-cache search package

Since apt-cache only uses the package cache on the system, make sure that this cache is up to date:

apt-get update

You can also use the utility apt-file if you know the name of a file you want to search for; this has to be added to the system however. For example:

apt-file search somefilename

I tend to use apt-cache in one of the following ways:

apt-cache search package | sort | grep item

(This shows you things that have item actually in their summary or names.)

apt-cache search thing | sort | less

(This searches for thing then sorts it for pleasant viewing with less.)