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 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.

10.07.2009 às 3:06
Cara, valeu!
Muito obrigado!
11.09.2010 às 13:54
Obrigado!
Sempre tive essa dúvida e ela nunca tinha sido respondida até agora!
22.10.2010 às 16:17
Optimo.
18.12.2012 às 19:24
Valeu. Muito esclarecedor.!
30.01.2016 às 16:57
Muito obrigado, plenamente esclarecedor.