> apt-cache search <regex>
> 	Searched through the package lists on the local machine for said
> regex.

Sometimes the search doenst find things, I find at times 

apt-cache pkgnames | grep <whatever> sometimes finds things better, but
search is definitely the debian recommend way.

Derek