Obrigado pelas respostas, mas acredito que eu não tenha sido claro com o meu problema.
No final, consegui compreender/resolver, então vou relatar aqui para futuros leitores.
1- Primeiro eu extrai o programa e joguei a pasta contendo os arquivos dele na pasta "/opt/".
2- Depois eu coloquei o arquivo ".desktop" na pasta "/usr/share/applications".
3- Por fim, eu coloquei o ícone do programa ".png" na pasta "/usr/share/pixmaps".
Com isso eu tenho a aplicação instalada e posso abrir pelo menu de aplicações.
Obs:
Pode ser que em algum outro sistema, a imagem dos ícones não fiquem armazenadas em "/usr/share/pixmaps". E a imagem do ícone não precisa ser necessariamente ".png".
O principal ponto aqui é o arquivo ".desktop", você deve especificar o caminho exato para o programa dentro dele, por exemplo, em "Exec=/opt/nome_do_programa %F" você deve passar o local exato do executável do seu programa(acredito que possa ser qualquer diretório), em "Name=Nome_do_programa", você especifica nome do programa, e em "Icon=imagem_do_icone_sem_extensão", a imagem do ícone(se não passar um caminho, ele vai interpretar como se a imagem estivesse em "/usr/share/pixmaps"(pelo menos no ubuntu))
No final das contas, não importa as pastas em que o programa esteja, e sim o ".desktop" explicando onde estão os arquivos do programa!
Lembrando que o caminho pro ".desktop" não varia, no caso do ubuntu por exemplo ele deve sempre estar em "/usr/share/applications"
É claro, o programa baixado(que não tenha instalador e que tenha sido distribuído por uma pasta zipada contendo os arquivos(como nesse caso)) pode ser executado diretamente não importa a pasta em que esteja, oque foi apresentado é apenas uma forma de listar o programa junto com os outros no menu de aplicações do sistema.
Tenham uma boa noite!