Hoy me he encontrado con un programita que puede resultar muy útil, apt-file. Te dice en qué paquete encontrar ese archivo que (por ejemplo) te pide cuando intentas compilar y no sabes donde encontrarlo.

Es para Ubuntu (y Debian supongo), y es muy fácil de instalar y usar:

Instalar:

sudo aptitude install apt-file
sudo apt-file update

Buscar archivo:

apt-file search archivo