Ubuntu Package List: Available vs. Installed

apt-cache pkgnames : lists all available packages
dpkg -l : lists all installed packages (Can apt-cache do it?)

Also useful:

apt-get update : updates the local list of available packages
apt-cache search : lists all available packages matching


Reference: http://www.debian.org/doc/manuals/apt-howto/index.en.html