Isso dependerá muito da distribuição que você estiver utilizando. Nas distribuições baseadas em Debian, como Ubuntu, é utilizado o apt para gerenciar pacotes. Para desinstalar completamente um pacote pelo apt utilize:
sudo apt-get --purge remove nomedopacote
Note que utilizei o atributo "--purge", que determina a remoção de todos os resíduos do pacote.
Após desinstalar com o comando acima, é interessante remover pacotes desnecessários que por ventura sejam deixados para trás:
sudo apt-get --purge autoremove
O comando é parecido com o anterior, porém, onde deveria estar o nome do pacote colocamos "autoremove" para que ele selecione automaticamente os pacotes desnecessários que podem ser removidos sem problemas.
Finalmente, os pacotes do programa devem ter sido totalmente removidos, porém, alguns arquivos de configuração podem ter permanecido em sua pasta pessoal, geralmente no diretório .config com o nome do programa ou na sua home, com um "." antes do nome para que o diretório fique oculto. Se quiser, pode removê-los caso deseje executar uma instalação limpa do programa futuramente ou liberar espaço em disco.