Os programas reais executáveis geralmente estão na pasta /usr/bin , embora a documentação, as bibliotecas de suporte e outros arquivos possam estar em pastas diferentes em todo o sistema de arquivos. Não há uma pasta específica em que elas acabem; é por isso que o gerente de software está lá, para acompanhar esse tipo de coisa.
(Você notará que as pastas são diferentes nos sistemas Linux, em comparação com o Windows - não há unidade C:, apenas um "diretório raiz" chamado / , com muitos subdiretórios.)
Para a maioria dos softwares, um ícone deve ser criado automaticamente para que você não precise lidar com os detalhes técnicos.
(Para ver os arquivos associados a um pacote em particular, veja esta questão AskUbuntu: