I didn't know much at all about gaming mice but I liked the Microsoft Sidewinder X8. One day I saw it on sale on Newegg for much cheaper than it normally was and bought it. Overall, I'm quite pleased. Not only is this mouse better than what I had before, it is wireless, so that was a big improvement. I find that while it has two programmable keys on the side, I usually only use them when browsing and not for anything special in-game.
It also fits in my hand quite comfortably. Anyway, what I've found the most helpful is actually seeing the mouse for yourself. It is very easy to get caught up in the specifications and what other people say about a mouse, but the most helpful advice I can give you is this: Go to a store that has the mice you're looking at, and get your hands on them.
Oh, and brands that I hear are good:
Microsoft (meh, I like mine, but they don't seem to make many others)
I'm never sarcastic.