Você tem que habilitar todos os repositórios do Ubuntu.
Eu editei o arquivo /etc/apt/sources.list e tirei o comentário das linhas que começam com deb.
Depois tem que fazer:
sudo apt-get update
sudo apt-get install zsnes
Ou pelo Gerenciador de Pacotes synaptic:
Sistema --> Administração --> Gerenciador de Pacotes Synaptic
Configurações --> Repositórios
Marque os repositórios que não estiverem marcados.
Depois selecione recarregar para atualizar a lista de pacotes.
Clique em procurar e digite zsnes.
[ ]'s.