Similar interests are important, I think. I do have a girlfriend, and she enjoys many of the same things I do--Japanese Internet memes, Nico Nico Douga, Touhou, j-core and speedcore, etc. It does help to have some VIP QUALITY, and since she has the right background I've started to give her some lessons on VIP. I taught her how to bu-n recently, although she's too shy to do it in public as of now...
As for looks, my only criteria usually are not morbidly obese and "cute" (subjectively speaking) hair.