Как выяснить, в каком пакете что-то есть, не прибегая к Google?

Ubuntu довольно умный. Просто попробуйте запустить его.

$ sphinx-build

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

Мне нравится использовать http://packages.ubuntu.com/ - там есть "Поиск содержимого пакетов". Debian также имеет аналогичный интерфейс на http://packages.debian.org/.

Это имеет то преимущество, что вы можете использовать его без CLI-доступа к самой Ubuntu, например, объясняя все по телефону.

Я не знаю, сможет ли это сделать apt-get, но я все равно предпочитаю использовать aptitude.

Используя его команду поиска, вы получаете список пакетов, который содержит искомую строку, однако он еще не полностью отвечает на ваш вопрос, так как не показывает, какой пакет содержит искомый бинарный файл.

Пример:

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

Вы можете использовать группу команд apt или aptitude, которые я рекомендую выше apt. Вот список для поиска

APT

Чтобы найти что-то похожее на команду, которую вы хотите:apt-cache search X например apt-cache search cheese даст вам все, что связано с сыром.
Чтобы показать, какие зависимости и вещи у вас есть, вы бы сделали apt-cache show cheese,
Конечно установить бы apt-get install cheese,

APTITUDE

Искать: aptitude search cheese который покажет более хороший список, чем apt
Показывать: aptitude show cheese который снова покажет более приятный и дружелюбный список
Установить: aptitude install cheese установить его. Опять приятнее.

Также aptitude предоставляет более релевантную информацию о том, что вы ищете, например:

apt-cache search phi В.С. aptitude search phi
apt-cache search sphi В.С. aptitude search sphi

Если вам нужна версия с графическим интерфейсом, я рекомендую Synaptic Package Manager или более простой Software Center. В Synaptic вы можете найти что-то похожее на то, что вы ищете, и оно покажет вам это.

авто-склонные

auto-apt пакет, который очень пригодится, особенно с Makefiles и configure скрипты, которые ссылаются на вещи, которых у вас может не быть, и не знают, где их найти, что часто бывает сложно с заголовочными файлами. Вы вызвали make в этом случае, и он пытался вызвать sphinx-build, но не удалось, когда он не смог его найти.

auto-apt run [...] выполнит указанную команду, а затем проведет вас через установку пакетов, содержащих отсутствующие файлы, которые она знает apt-get можно найти и установить.

Так что просто вызовите auto-apt run make html и посмотрим что получится:)

Для получения дополнительной информации см. Документацию для auto-apt.