"apt-cache search" does AND search over everything by default which is neat to find software for something. with aptitude you have to use some cryptic flags for that.

to look for packages that you have installed use "dpkg -l"

aptitude is otherwise great and I prefer it over apt-get