A principal diferença entre os dois é que o controle de dependências dos pacotes é mais completo e sofisticado no aptitude do que o do apt-get.
Mesmo, no caso de se querer corrigir problemas no sistema, o aptitude é muito mais eficiente. Por exemplo, o apt-get instala o pacote e as suas dependências como o aptitude, mas para desinstalar/remover um pacote o apt-get
desinstala apenas o pacote solicitado e deixa as dependências enquanto que o aptitude desinstala também as
dependências do pacote.
Já relativamente à pesquisa de pacotes o apt-cache search gera muito mais resultados do que o aptitude search.
Isto porque o comando apt-cache search nome_do_pacote procura pelo nome do pacote tanto no nome do pacote
como na sua descrição, enquanto que o comando aptitude search nome_do_pacote procura pelo pacote apenas no
nome dos pacotes.
Por estes motivos convém seguir a regra: procurar um pacote com apt-cache search e instalá-lo com aptitude install.
fonte: apostila do Ygor Abreu.