How do I figure out what package something is in without resorting to Google?

I often find myself wanting to install something, but I'm unsure of what package it's in. This is a very common occurrence for me:

$ make html
sphinx-build -b djangohtml -d _build/doctrees   . _build/html
make: sphinx-build: Command not found
make: *** [html] Error 127

$ sudo apt-get install sphinx
E: Unable to locate package sphinx

$ sudo apt-get install sphinx-build
E: Unable to locate package sphinx-build

googles

$ sudo apt-get install python-sphinx

Is there a better way?

Install apt-file and run apt-file update

Then use apt-file search sphinx-build to search for packages contanining a file named sphinx-build

Ubuntu is pretty smart. Just try to run it.

$ sphinx-build

The program 'sphinx-build' is currently not installed.  You can install it by typing:
sudo apt-get install python-sphinx

I don't know if apt-get can do it, but I prefer to use aptitude anyway.

Using its search command, you get a list of packages that contains the string you are searching for, however that still does not fully answer your question, as it does not reveal which package contains the binary you are looking for.

Example:

sudo aptitude search sphinx
p   gstreamer0.10-pocketsphinx      - lightweight speech recognition - GStreamer
p   libpocketsphinx-dev             - lightweight speech recognition - developme
p   libpocketsphinx1                - lightweight speech recognition - library  
p   libsphinx-search-perl           - Perl module for Sphinx search engine      
p   libsphinx2-dev                  - speech recognition library - development k
p   libsphinx2g0                    - speech recognition library                
p   libsphinxbase-dev               - Sphinx base libraries - development files 
p   libsphinxbase1                  - Sphinx base libraries                     
p   pocketsphinx-hmm-tidigits       - lightweight speech recognition - TIDIGITS 
p   pocketsphinx-hmm-wsj1           - lightweight speech recognition - WSJ1 acou
p   pocketsphinx-lm-wsj             - lightweight speech recognition - WSJ langu
p   pocketsphinx-utils              - lightweight speech recognition - command-l
p   python-pocketsphinx             - lightweight speech recognition - Python mo
p   python-pocketsphinx-dbg         - lightweight speech recognition - Python mo
p   python-repoze.sphinx.autointerf - Sphinx extension that auto-generates API d
p   python-sphinx                   - tool for producing documentation for Pytho
p   python-sphinxbase               - Sphinx base libraries - Python module     
p   python-sphinxbase-dbg           - Sphinx base libraries - Python module (deb
v   python2.6-pocketsphinx          -                                           
v   python2.6-pocketsphinx-dbg      -                                           
v   python2.6-sphinxbase            -                                           
v   python2.6-sphinxbase-dbg        -                                           
v   python2.7-pocketsphinx          -                                           
v   python2.7-pocketsphinx-dbg      -                                           
v   python2.7-sphinxbase            -                                           
v   python2.7-sphinxbase-dbg        -                                           
p   sphinx2-bin                     - speech recognition utilities              
p   sphinx2-hmm-6k                  - speech recognition library - default acous
p   sphinxbase-utils                - Sphinx base libraries - utilities         
p   sphinxsearch                    - Fast standalone full-text SQL search engine

I like to use http://packages.ubuntu.com/ -- there's "Search the contents of packages" inside. Debian also has similar interface at http://packages.debian.org.

This has the advantage that you can use it without CLI access to Ubuntu itself, f.e. explaining things over a phone.

you can use the apt group of commands or aptitude which i recommend above apt. Here is the list to search

APT

To search for something similar to the command you want: apt-cache search X for example apt-cache search cheese will give you everything related to cheese.
To show what dependencies and stuff it has you would do apt-cache show cheese.
Of course to install would be apt-get install cheese.

APTITUDE

To search: aptitude search cheese which will show a more nicer list than apt
To show: aptitude show cheese which again will show a more nicer and friendlier list
To install: aptitude install cheese to install it. Again nicer.

Also aptitude gives more relevant information to what you are looking for, for example:

apt-cache search phi VS aptitude search phi
apt-cache search sphi VS aptitude search sphi

If you want a GUI version i recommend Synaptic Package Manager or a simpler Software Center. In Synaptic you can look for something similar to what you are looking for and it will show it to you.