Just created a Debian package for the Sega Megadrive emulator Gens. Anyone wanna test it out? See here
Cool, how did you do that?
Did it work for you? 
I made the Debian package when I was compiling Gens. See here for instructions.
As for setting up K Menu entries, that was a bit more tricky. See, most programs will add themselves to the menu once you’ve compilied them, but Gens didn’t. Basically I made a .desktop file and copied it to the .deb file.
If you remember, I made a thread about not being able to install Kaffeine 0.8.2. Well in the end I compiled it from source on a VMware machine and made a Debian package of it. Then I just installed it with dpkg on my main Kubuntu box