É preciso criar um arquivo com o conteúdo deste tipo:
#!/usr/bin/env xdg-open
[Desktop Entry]
Version=1.0
Type=Application
Terminal=true
Icon[pt_BR]=
Name[pt_BR]=
Exec=EXECUTAVEL_QUE_DEVE_ESTAR_NA+PASTA_/USR/BIN
Comment[pt_BR]=bla_bla_bla
Name=Nome_Aplicativo
Comment=Aplicativo
Icon=
Note o parâmetro Terminal=true!
Salvar no Desktop com a extensão .desktop e depois dar permissão de execução.