[bashinator]

    dpkg -S /some/file # tells you what package provides that file  
    dpkg -L some-package # lists all the files provided by a package
    apt-get search <regex> # lists all package names matching <regex>

[cben]

$ apt-get search foo E: Invalid operation search

It's apt-cache search, and it searches full descriptions, not just package names.

[bashinator]

My bad - I meant `aptitude search`