Receta rápida: quiero instalar curl-config. El problema es que no existe ningún paquete .deb con ese nombre. Y buscando con apt-cache search curl | grep dev , me salen unos cuantos. ¿Cuál de esos paquetes ofrece curl-config? Seguro que te ha pasado antes (no con curl-config pero sí con otro nombre de binario)
Solución: consúltalo en http://packages.ubuntu.com/ (search the contents of package)
Update: gracias a Diego y Ubuj me entero de la existencia de apt-file, una aplicación que hace justo lo que acabo de comentar: busca en el contenido de los paquetes ofrecidos por el repositorio que queramos (en mi caso Ubuntu) el fichero que le digamos. Lógicamente lo primero que hay que hacer es instalar apt-file y a continuación pedir un update (apt-file update , para que se descargue la información del repositorio). A partir de ahí, buscar el nombre del paquete que ofrece el fichero que quieres es fácil:
$ apt-file search curl-config