Vale a visita sobre o assunto no blog do Goncin.
Ambos são frontends para o dpkg, o sistema de gerenciamento de pacotes do Debian, e como tal herdado pelas distros filhas. O aptitude nasceu como uma interface orientada a menus em modo terminal, mas também pode (e deve) ser utilizado na linha de comando. O apt-get, por seu turno, faz parte de um conjunto (o qual inclui ainda o apt-cache, o apt-file e o apt-cdrom) de comandos de terminal, e portanto não tem nada parecido com “menuzinhos”.
Se ambos podem ser utilizados praticamente da mesma forma, então qual a diferença entre eles? Vamos aos fatos.