Je crois qu'apt-file vous donnera ce que vous voulez.
$ apt-file update
$ apt-file list mysqladmin
kmysqladmin: /usr/bin/kmysqladmin
$ apt-file search mysqladmin
autoconf-archive: /usr/share/aclocal/ac_prog_mysqladmin.m4
autoconf-archive: /usr/share/autoconf-archive/html/ac_prog_mysqladmin.html
bash-completion: /etc/bash_completion.d/mysqladmin
kmysqladmin: /usr/bin/kmysqladmin
$ apt-file search mysqladmin
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_health.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.dtd
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_startup_variables_description.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_status_variables.xml
mysql-admin: /usr/share/mysql-gui/administrator/mysqladmin_system_variables.xml
mysql-client-5.1: /usr/bin/mysqladmin
mysql-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-cluster-client-5.1: /usr/bin/mysqladmin
mysql-cluster-client-5.1: /usr/share/man/man1/mysqladmin.1.gz
mysql-testsuite: /usr/lib/mysql-testsuite/r/mysqladmin.result
mysql-testsuite: /usr/lib/mysql-testsuite/t/mysqladmin.test
J'utilise dpkg -S filename pour ça. Il ne peut pas rechercher des fichiers qui ne sont pas installés sur votre système avec lui, mais il est livré par défaut dans toutes les distributions dpkg alors que apt-file ne l'est pas.
Vous pouvez également rechercher des fichiers qui ne sont pas installés sur votre système à l'aide du site Web http://packages.ubuntu.com/.