No Debian ou Ubuntu, você pode perguntar ao seu gerenciador de pacotes sobre pacotes instalados
dpkg --search <filename>
Se o pacote não estiver instalado, você pode usar apt-file
apt-file update
apt-file search <filename>
Se você não sabe nada sobre o arquivo específico que está procurando, mas quer saber sobre alguma funcionalidade específica (mencionada na descrição do pacote)
apt-cache search <keywords>
Para procurar um pacote quando você conhece parte do nome (mesmo que o pacote não esteja instalado)
dpkg -l '*pattern*'