I can find it listed when I search for "zsnes" in the Ubuntu Software Center but it doesn't have the "Install" button. If I click the "More information" button I'll get a "package not found" message.

Synaptic can't find this package either.

(from user @REJ) I have Natty 64bit. When I run sudo apt-get install zsnes it gives the following output:

Reading package lists... Done Building dependency tree
Reading state information... Done Package zsnes is not available, but is referred to by another package. This may mean that the package is missing, has been obsoleted, or is only available from another source

E: Package 'zsnes' has no installation candidate