Você pode usar apt-file (não é instalado por padrão no Ubuntu). Antes do primeiro uso, execute apt-file update para buscar arquivos de conteúdo do apt-sources.
Aqui está um exemplo:
apt-file -F list geany | egrep -w "(s|)bin"
geany: /usr/bin/geany
E um exemplo com um pacote com mais comandos:
apt-file -F list mesa-utils | egrep -w "(s|)bin"
mesa-utils: /usr/bin/glxdemo
mesa-utils: /usr/bin/glxgears
mesa-utils: /usr/bin/glxheads
mesa-utils: /usr/bin/glxinfo
Nesse caso, os comandos são, evidentemente: glxdemo , glxgears , glxheads e glxinfo .