I have not used debian based distros in years. currently on my Pi I am running http://www.raspbmc.com/
a pure media server that is built on a debian (apt-get) system.
years past you could apt-get search foo and get a response much like yum search.
well according to apt-get --help, that is no longer an option, so how does on in the dpackage world search via apt-get?