Não é incomum, quando não temos experiência em shell, passar por uma situação dessas:

$ ./script.sh
-bash: ./script.sh: Permission denied

Antes de sair olhando se há algo errado com o script, vamos analisar a mensagem de erro em pt_BR: Permissão negada. Diferente de outros sistemas operacionais, no mundo *nix o que faz de um arquivo um programa executável não é a sua extensão e sim as suas permissões.

Resumidamente, existem 3 permissões básicas quando se trata de arquivos: ler, escrever e (finalmente) executar (representado pelas letras r,w e x, respectivamente). Isto é o que impede um usuário de conseguir ler os documentos de outro, por exemplo. Então, um programa, para ser executado, precisa ter esta permissão correspondente, e ai entra o comando chmod.

$ ls -l script.sh
-rw-r--r--  1 peczenyj users 22 2007-07-26 11:08 script.sh
$ chmod +x script.sh  # vamos ativar o bit de execução (x)
$ ls -l script.sh
-rwxr-xr-x  1 peczenyj users 22 2007-07-26 11:08 ./script.sh
$ ./script.sh         #agora sim!!!
oi

Problema resolvido.