TheGreatImber gives a good description for REXing, though I'm not sure Patronage is absolutely neccessary. When doing a REX you won't get that many SP's anyway. I'd also take 5. and 6. as more guidelines than rules. In terms of picking a civ, generally you'd want to go for a civ that:
1) Has a per city hapiness bonus (usually in the form of a UB), e.g. Egypt for an early expansion (though the UA suffers for this), Persia for slightly later or the Celts for later still (but they tie in with 2) as well). A late 'tall and wide' strategy with India is also possible. These will help you avoid hapiness issues. Or....
2) Has early religion bonuses, e.g. the Celts, Ethiopia (though this ruins the UA), Mayans, Byzantines. This will help get and spread a religion with the best hapiness bonuses, as hapiness is what religion does best. Or....
3) Has production bonuses e.g. Rome, Russia, possibly Iroqois. The reward for REXing is in massive production and/or gold, so a civ that magnifies these benefits is using REXing well. Or....
4) Has trade route and/or gold bonuses, e.g. Arabia, Inca, Carthage. More cities = more trade routes. Or....
5) Has another kind of per city benefit, e.g. France. Good for REXing beginners as you can still get a few SP's this way (It's usually what you give up when you REX).
Right, I've probably said almost half the civs by now (and that's not including the civs I forgot about), so I'll shut up and let you try some out. Happy REXing!
P.S I basically never go for a science vc so I don't know what the optimal science victory strategy is, but if REXing is good for science then Korea and Babylon might be good too. Dunno, seems like a REX means land coveting and RA difficulty......