Eu testei isso e funcionou bem. Garanta que seu script comece com o hash-bang correto, por exemplo, #!/bin/bash
Em seguida, siga estas etapas:
Pressione Alt + F2 , digite dconf-editor
e pressione Enter .
No dconfg-editor goto: org ➤ gnome ➤ nautilus ➤ preferences
Clique em executable-text-activation
e, no menu suspenso, selecione:
launch : para iniciar scripts como programas.
OR
pergunte : para perguntar o que fazer através de um diálogo.
Feche o editor do dconf. É isso!
Fonte: Como eu executo scripts executáveis no Nautilus? Responda gentilmente de Basharat Sial.