Você deve poder usar isso para executar o arquivo:
./script.sh
ou para obter outro terminal para executá-lo com:
gnome-terminal script.sh
./ significa procurar no diretório atual, isso geralmente não é necessário se prefixado por um comando, o que seria procurado no diretório atual se nenhuma pasta fosse especificada.
Certifique-se de que é executável com chmod +x script.sh .
Nautilus pode fazer outras coisas em vez de apenas executá-lo, procure nas preferências em Behavior :
