Você pode ver o conteúdo de um arquivo deb instalado assim:
dpkg -L some-GBA-package
Ou se criar muita saída:
dpkg -L some-GBA-package | less
Ou para ver o conteúdo do seu arquivo deb baixado:
dpkg --contents some-GBA-package.deb
Acabei de instalá-lo (visualboyadvance-gtk) e o encontrei na entrada do meu menu. Olhando para o que é lançado, é o comando:
gvba
Tente esse comando em um terminal.