Clique com o botão direito no arquivo e marque o botão Permitir execução do arquivo como programa na guia de permissão
Em seguida, clique duas vezes no arquivo e escolha executar ou executar no terminal (se for um aplicativo de console)
Nota:
Isto não funcionará se o programa precisar de permissão de root