Acho que clicando duas vezes no arquivo, o nautilus já executa ele normalmente (bin, run). Os casos onde isso não acontecem por padrão, são quando o arquivo não tem permissão pra ser executado (o que é uma coisa ótima, e é por isso que o linux é tão seguro), o que pode ser remediado rapidamente clicando com o botão direito, depois propriedades, permissões.
Ou, se quiser mesmo dinamismo no trabalho, abra o terminal e:
chmod +x nome-do-arq
./nome-do-arq
Eu pessoalmente acho o segundo bem mais rápido.