If you've used Debian aptitude to search for packages, you'll have seen the character entries that are returned along with your search results.
# aptitude search emacs
p acl2-emacs - A Computational Logic
i emacs - The GNU Emacs editor (metapackage)
id emacs-chess - a client for playing Chess
i A emacs23 - The GNU Emacs editor (with GTK+)
p emacs23-el - GNU Emacs LISP (.el) files
v A emacs23-gtk -
ppA emacs23-nox - The GNU Emacs editor (without X)
v emacsen -
What do the characters mean?
The first character of each line indicates the current state of the package. The most common states are:
p no trace of the package exists on the system
c the package was deleted its config files remain
i the package is installed
v the package is virtual
The second character indicates the stored action to be performed on the package. The most common actions are:
i the package will be installed
d the package will be deleted, and
p the package and config files will be removed
[Blank space] no action to be performed
The third character if shown, indicates:
A the package was automatically installed
Hope this helps interpret your search results.