Como desinstalar um programa sem deixar rastros ?

Cada programa é diferente. Para realmente desinstalar um programa 100%, você tem que saber cada um dos arquivos que ele cria ao ser instalado e utilizado. Os processos de desinstalação em geral removem somente os arquivos gerados durante a instalação e não durante o uso, podendo restar arquivos residuais que precisam ser removidos à mão.

Luan, segundo a manpage do apt:

          Removing a package removes all packaged data, but
           leaves usually small (modified) user configuration
           files behind, in case the remove was an accident.
           Just issuing an installation request for the
           accidentally removed package will restore its
           function as before in that case. On the other hand
           you can get rid of these leftovers by calling purge
           even on already removed packages. Note that this does
           not affect any data or configuration stored in your
           home directory.

Vou tentar traduzir mais ou menos pra quem entende pouco de inglês:

Remover um pacote remove todos os dados empacotados, mas deixa geralmente pequenos arquivos de configurações de usuário (modificadas) pra trás, no caso da desinstalação/remoção ter sido um acidente. Bastando solicitar uma nova instalção do pacote acidentalmente removido para que suas funções sejam restauradas como antes. Por outro lado você pode se livrar desses "deixados pra trás" chamando "purge" mesmo em pacotes já removidos. Note que isto não afeta qualquer dado ou configuração guardados no seu diretório home.

Então basta chamar o purge:

sudo apt purge nomeDoPrograma

Ele removerá o programa e não deixará arquivos pra trás. Se já tiver removido o programa com remove também pode utilizar o mesmo comando.