sudo apt-get install gdebi-core
Note que, em geral, você pode procurar pacotes usando:
apt-cache search <search_term>
Então, por exemplo:
apt-cache search gdebi
retorna informações sobre os pacotes gdebi-core , gdebi (GUI do GNOME) e gdebi-kde (KDE GUI).