Apple says that the 1gig iPod shuffle holds 240 songs, so that's probably a decent basic guide for MP3 capacity.
You can crunch the data smaller (with a trade-off in quality) to get more on there. My MP3s are all LAME encoded VBRs, but if I want to smoosh alot on a stick, I'll make 64k CBRs instead. The quality of your headphones and preference for sound quality may help guide you there too.
I use
PSP Video 9 to rip from DVD to the PSP format. It lets you tune the aspect ratio, frame rate, audio quality, and resolution to get whatever trade-off in size and quality that you'd like. I usually rip episodic content (TV shows) rather than whole movies so I never really paid attention to file sizes. You should probably do some experimenting to find out what's best for you.
The important thing is that you can get
lots of NES/SNES/Genesis ROMs onto a 1gig stick!

-pmc