dpkg, através do apt ou aptitude mantém um banco de dados do software instalado em /var/lib/dpkg/status
.
Você pode saber mais sobre este aqui .
Minha resposta é baseada em uma resposta dada nesta discussão no fórum .
Como apontado pelo @psusi, porque apt e aptitude são apenas front-ends para o dpkg, na verdade é o dpkg que acompanha o empacotamento.