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)  

NOTE: aptitude search foo is slower than using apt-cache search foo to perform a searc. The output is also a bit different from apt-cache. Use whichever method is preferred.