For gaming, the most important factor of sound quality is positional accuracy. A lovely sounding pair of headphones won't do you much good if you can't pinpoint sound effects designed to give you clues about your surroundings. A footstep or the creak of a door can warn you of approaching danger. The sound of a gunshot, in a well designed game, can be located sonically and allow you to zero in on the source. The sound of a waterfall as it pans around you as you turn your character in-game can add an extra bit of atmosphere to the scene. All of these depend on the headphone/headset's ability to accurately position audio in a sound-space. While this is useful in movies and music, it's crucial for games.
Ideally we want this in headphone form.
Stereo vs Surround Sound
This naturally brings us to the stereo vs. surround sound debate. In theory, a set of surround sound speakers or headphones will sound at least as good as a stereo set when playing a stereo source and significantly better when playing a surround sound audio source. However, this rarely pans out, especially when you are talking about headphones. With surround sound speakers, the rear/surround speakers sound like they are coming from behind you, in part, because the sound they produce have a room to bounce around and the speakers are physically located behind you. These room acoustic properties are important to the surround sound effect and they are difficult to reproduce when the "room" is a tiny headphone ear cup.
A surround sound headphone or headset will need to emulate room acoustics to some degree in order to trick our ears into thinking the sound is coming from behind us. This is, in essence, how most "virtual surround sound" technologies work. This is either done with digital sound processing to simulate the effects of room acoustics, or in analog by using several physical drivers (speakers) per ear and innovative ear cup design. Both of these methods work, and don't, to some degree. The quality of the effect also varies wildly depending on the product. The surround sound headphones that do a good job sound really good. The ones that don't can sound absolutely awful.
The argument for stereo is to keep it simple. Instead of dealing with a ton of digital processing and trickery, which can ruin sound quality in pursuit of better sound positioning, just stick to two high quality channels. While you don't get the same audio experience, a quality set of stereo headphones can still offer excellent sound positioning. You won't ever get the impression that the sounds are truly coming from behind you, like with a quality surround sound setup, but a good stereo setup can still give you a decent approximation.
Stereo is also the way to go if sound quality is your utmost concern. The digital processing required for virtual surround sound introduces sound artifacts and distortion, altering the original signal and creating signal noise. Using several speakers per ear cup for "true" analog surround sound also produces problems as the sound waves created by the speakers will interact and combine in complex ways, potentially reducing sound quality. A single high quality speaker per ear is still the best setup for sonic clarity and accuracy.
Comfort & Durability
For a gaming application, headphones and headsets must be comfortable and durable. They should be light and non-fatiguing since they'll often be worn for hours at a time. They must also endure plenty of punishment and be able to survive their fair share of gaming marathons. There are a variety of headphone styles but the most comfortable for extended use tends to be a circumaural cup design where the cushioned area of the ear cup goes around the ear and rests against the head. This is opposed to designs where the ear cup sits on the ear, called super-aural, which can become uncomfortable during extended use. In-ear designs are very popular right now, but many people find them uncomfortable and they also pose a much greater risk to your hearing if you're in the habit of cranking the volume.
Headphone vs Headset
The difference is simple, a headset has a built-in microphone while a headphone doesn't. Usually the mic is on a boom arm of some sort which holds it close to the user's mouth. The primary advantage a headset has over a headphone is the convenience of having a built-in microphone solution. However, don't be afraid to consider regular headphones, even if you plan on using a mic often. It's possible to pick up a small lapel mic that clips right onto the headphone cord, or your shirt, for a few bucks that will provide a similar level of functionality as a headset mic. Sound quality, comfort and other considerations should come first.
Budget & Value
A good set of gaming headphones doesn't have to be expensive, but it can be. Good gaming headphones range from under $50 to over $300. However, be warned that many of the cheapest solutions aren't much better than a set of basic iPod earbuds. Having said that, price isn't the best way to determine an item's quality either. Some of the most expensive solutions aren't always so great and many of the better solutions are priced in the lower-middle of the pack.