Search for packages with “foo” in the name:

aptitude search foo

Search for installed packages with “foot” in the name:

aptitude search '~foo'

Search for packages from the section “foo” that are not installed:

aptitude search \!~i~sfoo

Pipelines allow complex searches:

aptitude search '~i' | grep -ie 'x11\|xorg' | less

Looking for packages installed from anything else than stable:

aptitude search '?narrow(?installed, !?archive(stable))'

Looking for packages installed from testing (assuming you have sources lists with stable and testing repositories):

aptitude search '?narrow(?installed, ?archive(testing) !?archive(stable))'

Shows all packages which are installed on your system because some other package recommends it, but they are not actually dependencies of packages:

aptitude search '?and( ?automatic(?reverse-recommends(?installed)), ?not(?automatic(?reverse-depends(?installed))) )' 

can give something like this:

i A apt-xapian-index    -   maintenance and search tools for a Xapian index of Debian packages 
i A exim4               -   metapackage to ease Exim MTA (v4) installation 
i A file                -   Determines file type using "magic" numbers 
i A heirloom-mailx      -   feature-rich BSD mail(1)  

To determine why an automatically installed package is present on the system:

aptitude why python-debian

Returns something like:

i   aptitude         Recommends apt-xapian-index         
i A apt-xapian-index Depends    python-debian (>= 0.1.15)

The first column of information displayed in the package list in the top pane, when actually viewing packages lists the current state of the package, and uses the following key to describe the state of the package:

• i: Installed package
• c: Package not installed, but package configuration remains on system
• p: Purged from system
• v: Virtual package
• B: Broken package
• u: Unpacked files, but package not yet configured
• C: Half-configured - Configuration failed and requires fix
• H: Half-installed - Removal failed and requires fix

NOTE: aptitude search foo is slower than using apt-cache search foo to perform a search.

The output is also a bit different from apt-cache.

Use whichever method is preferred.