Você precisa mudar o comportamento do Nautilus.
Abra o Nautilus - Arquivo - Preferências (Opções) - Guia Comportamento. Em "Arquivos de texto executáveis", marque "Executar ..." ou apenas "Perguntar ..." e, em seguida, você tem a opção.
Eu li várias respostas dizendo que, se eu alterar as propriedades do arquivo para definir o 'Permitir executar como programa', ele permitirá que eu clique duas vezes no arquivo e ele será iniciado.
Em vez disso, quando tento fazer isso para um arquivo .sh, ele é aberto por meio do gedit.
Eu também tentei chmod ugo + x o arquivo, mas isso não ajudou.
Você precisa mudar o comportamento do Nautilus.
Abra o Nautilus - Arquivo - Preferências (Opções) - Guia Comportamento. Em "Arquivos de texto executáveis", marque "Executar ..." ou apenas "Perguntar ..." e, em seguida, você tem a opção.