Ola
Tudo depende de como voce administra o sistema.
Diferente do Windows que tem tudo pré automatizado, no GNU/Linux é você quem manda, não o sistema.
Alguns pacotes deixam rastros sim, geralmente em sua pasta pessoal em arquivos de configuração ocultos. Isto é proposital, pois assume-se que se instalou um pacote voce precisa dele e vai utilizar, assim ele guarda suas preferencias nestes arquivos ocultos, pois se precisar reinstalar, suas preferencias se manterão.
No caso então de se desejar remover o pacote e seus arquivos de configuração, use a opção --purge no dpkg ou no apt ou no aptitude.
No caso do registro do Windows, o pinguim não tem esta funcionalidade, logo nada a remover aqui.
Uma coisa comum no windows é ele não remover .dll's instaladas por programas com uninstall mal escritos. No Gnu/Linux é parecido, mas é possivel se remover as bibliotecas que ficaram com a opção autoremove no dpkg, no apt ou no aptitude.
O Windows sempre deixa algo na /temp ao desligar o sistema, já o Gnu/Linux nao deixa nada em /tmp
Arquivos de instalação ficam guardados em cachê, que podem ser removidos com o uso das opções clean e autoclean no dpkg, apt ou aptitude.
Já no Windows, arquivos de atualização ficam ocultos na pasta /Windows e não são removidos às vezes nem com programas de limpeza. Já no pinguim isto não acontece, e o sistema não "incha" como acontece nas janelas.
No Gnu/Linux você tem também outras opções de limpeza, como o nativo do Ubuntu, o deborphan e outros que prometem limpezas mais radicais. Porém lembre o que disse no inicio, de que voce é o dono do sistema, assim eles podem remover bibliotecas e arquivos de configuração que você não deseja, exigindo conhecimento do que se está fazendo por parte do administrador, que é você.
Para testes de pacotes, é costume se criar um usuario novo para isto, e depois de testado se remover os pacotes de teste e dar fim no usuario
Finalmente, sobram os arquivos do spool de impressão, que no Windows muitas vezes se recusam a sair da pasta /spool, mesmo reinicando o sistema precisando entrar em modo de segugrança, e blá, blá, blá, e que no Gnu/linux basta se entrar via browser no spool para remover os arquivos com toda a tranquilidade sem ter reiniciar nem o sistema nem o usuario.
No Windows, mesmo com todo o conhecimento requerido, às vezes um virus chato se instala e fica uma loucura remover ele "na unha", levando a necessidade de reinstalação do sistema (por desconhecimento da rotina do virus) e no Gnu/Linux isto não ocorre.
Podemos concluir então que conhecer o sistema a fundo é sempre a melhor alternativa, seja o sistema que for.
[]'s