O gerenciador de pacotes padrão no Ubuntu, apt (instalar um pacote com sudo apt-get install PACKAGE ) faz isso sozinho.
Por exemplo, se o pacote foobar dependesse dos pacotes foo e bar e você removesse foobar , não seria removido automaticamente , mas foo e bar serão removidos quando você executar o comando sudo apt-get autoremove
Deve-se notar que apt-get autoremove somente removerá uma dependência auto instalada se nenhum outro pacote precisar, para evitar que o seu sistema seja quebrado
aptitude é uma boa ferramenta se você quiser ler informações detalhadas sobre um pacote (sem instalá-lo) e suas dependências ou se você não tiver certeza do nome de um pacote e quiser procurá-lo