If it's not in your right click menu choices.
Just open up a terminal and type out.
gdebi-gtk
It will appear for you. Open your gens.deb in the open option in gdebi app. To install it.
http://segaretro.org/Gens/GS#Download
type locate gdebi to find the file structure.
locate gdebi
/usr/bin/gdebi
/usr/bin/gdebi-gtk
Also, it's worth noting that the emulators Sega use are pretty bad compared to Gens and Kega Fusion. If you feel guilty about pirating, you can buy the digital copy and then download the rom.
I've used Gens/GS successfully, and it supports save states just fine. There's a newer version of it (http://www.dusers.drexel.edu/gitweb/gitweb.cgi?p=~korth/gens-gs-ii.git;a=summary), but you have to compile it.