In order to stay cutting edge in gaming, chances are you'll eventually have to purchase a new video card. There's obviously a lot of choice out there. The two major GPU companies are ATI and nVidia. They make the vast majority of third party graphics chips in the world. New generations of chips are usually released on an annual basis. New generations are usually faster and provide new features. Currently available cards are ATI's HD 3000 and HD 4000 line and nVidia's Geforce 9 and GTX200 series. We'll stick with the HD 3000 line and Geforce 9 for the purpose of this article since the newer series of cards haven't seen a full releases yet.

GPU Variants and Naming
Generally, each generation is broken down into three segments. Enthusiast, mid-range, and entry level. Enthusiast represents the fastest and most powerful cards. They are usually the most expensive and consume the most power but offer the best performance and are most suitable for gaming. They usually cost over $300. Entry level cards are cheap, low power cards. They will provide better performance than onboard solutions due to having their own dedicated memory. They are suitable for desktop acceleration (Vista Aeroglass, Linux Compiz) and HD video acceleration. They use the least amount of electricity and produce the least amount of heat, making them ideal for a home theater PC. However, they are unsuitable for gaming. These are usually priced around $100 or lower. Mid-range cards represent a compromise between the two extremes. They are usually priced around $100 - $200. Mid-range cards are suitable for light to moderate gaming as well as every day use. They won't provide top performance but they generally offer a good bang for the buck. The following is a break down of current graphics cards based on their category.

Entry Level: ATI Radeon HD 3400, HD 2400 / nVidia Geforce 8400, Geforce 8500
Mid-Range: ATI Radeon HD 3600, HD 2600 / nVidia Geforce 8600, Geforce 9600
Enthusiast: ATI Radeon HD 3800, HD 2900 / nVidia Geforce 8800, Geforce 9800

Under each of the mentioned GPU series are sub cards, usually marked with higher numbers or stuff like "GS", "GT" or "GTX". Higher numbers usually means a better card. nVidia likes to use stuff like GT though ATI used to use it as well, but they no longer do. A GT card will be better than a GS card and a GTX is better than a GT. The number game can be confusing to first time buyers so it's a good idea to visit benchmarking sites to compare a card's performance to see if you're getting what you want.
Recently, some top line cards such as ATI's HD 3850 and 3870 have come down to around the $200 price point so there is some confusion as to whether they are mid-range or enthusiast. ATI has been working to produce a card with the best performance per dollar. In other words, they're trying to make their cards cheaper while still being at or on par with nVidia's top end cards. I woul classify them as enthusiast.

nVidia vs ATI/AMD
The ultimate question is whether you should go nVidia or ATI. There are a couple of factors, primarily depending on what you'll use the card for. nVidia currently takes the performance crown but their cards are more expensive. I currently use an HD 3850 from ATI. However, I find nVidia has better drivers and is more compatible with older games. nVidia is also more compatible with Linux if you want to run that OS. nVidia has a slight edge in OpenGL rendering too. ATI's current line of cards run cooler and consume less electricity than nVidia's. They also have a slight edge in DirectX rendering and are much cheaper at the enthusiast level. If you're looking for an enthusiast card, ATI is the way to go right now since you won't have to spend a lot of money to get something good.

Another point worth noting is that nVidia and ATI rarely release their own cards, they just make the GPUs. Third party companies assemble the components to the circuit board and usally add their own touches. Some companies use a basic reference design for the card where as others might integrate better memory, more memory, or different cooling techniques. In the end though, there really isn't a lot of difference other than build quality of the assembled product. Common companies that market graphics cards are Asus, Diamond, XFX, eVGA, and HIS but there are many more besides this.

Graphics Memory
Another thing to consider is the amount of memory (RAM) a card has as well as it's RAM type. All graphics cards today use GDDR which is soldered to the card itself and can't be upgraded. The amount of memory a card has doesn't really affect performance overall but rather performance at higher resolutions. For most people, a 256mb card will due if you're playing at 720p (1280x720) or in that ballpark. Even at 1080p, 256mb may be enough though I would suggest spending extra on a 512mb card. A common marketing gimmick is to put a lot of memory into entry-level or mid-range cards. Companies will sometimes put 512mb or even 1gb of memory into an entry-level card. This is useless since these cards can't even game at the resolutions that much memory would be required for. Since GDDR is cheap enough, it's not like you're getting hit in the wallet but don't be fooled into thinking more memory on the card is going to boost the speed to mid-range or enthusiast levels. Another marketing gimmick is Turbocaching (nVidia's term, ATI has something similar). This is a card that can use some of the computer's system memory while keeping a small amount of it's own dedicated RAM. The problem with this is that system RAM is slower than GDDR so you might be thinking you can have limitless memory for your card but in reality it's at a performance cost. It also consumes valuable system RAM space. This is frequently used in entry level cards.
In terms of performance, faster RAM is going to make a bigger performance difference than more RAM at the resolutions most typical gamers play at. Memory speed determines how quickly the memory can handle the data the GPU is giving it. You'll frequently see cards labeled GDDR2, GDDR3, or even GDDR5. That stands for "Graphics Double Data Rate [Generation #]. Most cards today are using GDDR3 or 4 while some are using the new GDDR5. Generally speaking, the newer the generation, the faster the memory. Since actual clock speeds usually aren't listed on the box, this is a good indicator of what you're getting. The actual clock speeds though can easily be found online. Faster (higher clocks) is better for gaming.
One final note on memory is the memory bandwidth, measured in bits. Entry level and mid-range cards should have at least 128-bit memory bandwidth while enthusiast cards should be 256-bit minimum. You might have to do some digging to find this info. This represents how much data can move between the GPU and it's memory at the same time. Bigger is better. High RAM speed with a high bandwidth gives optimum performance.

Connectivity
First of all, you'll need to determine what bus your card will need. There are two, PCIe (aka PCI Express) and AGP. This is used for connecting the card inside the computer. Most systems today use PCIe 16x since it is technically faster than the older AGP. If you have an older system, you'll need to specifically look for an AGP card. In reality there isn't a lot of performance difference right now but this will change as cards become more powerful. PCIe has the added advantage of allowing multiple graphics cards to be used in conjunction with each other through nVidia's SLI or ATI's Crossfire technology. Your motherboard will need to support one or the other to use this and will need two or more PCIe 16x compatible slots.
From there, you'll also need to determine what you're hooking the card up to. If you want to use an HDTV, you'll need a card that has an HDMI port or DVI-HDMI adapter, or one that has component video out. Most cards today do. Some cards now allow audio to pass through their built in HDMI port for easy connection to a home theater system. For HD video from Blu-ray or HD-DVD, you'll need a card that is HDCP compatible. HDCP stands for High Bandwidth Digital Copy Protection. Quite frankly, it's a marketing gimmick by Hollywood disguised as DRM. I firmly believe it was cooked up to force people with older HDTVs, graphics cards, and monitors to buy new hardware. If your card doesn't have it, it will reduce the image resolution of HD movies to that of a regular DVD. (There are ways to cheat it though) Most newer cards a have this chip. However, it only affects Blu-ray and HD-DVD, not HD gaming, free HD video downloaded off the web, or regular computer activities. However, it may affect commercial HD video downloaded from the web, though I don't know what DRM schemes various sites are using.

SLI and Crossfire
Some motherboards today allow you to use more than one graphics card. In order to use this feature your GPU must support it, which most today do. Your motherboard must also have two empty PCIe slots and support either nVidia's SLI (Scalable Link Interface) or ATI's Crossfire. Since it's controlled in the motherboard's chipset, the board can only support one or the other and not both. Your motherboard will indicate which it supports either on the manufacturer's website, on the box, or in the instruction manual.
SLI and Crossfire allow you to use up to four GPUs provided there are enough 16x PCIe compatible slots. There is a law of deminishing returns though meaning the performance boost gained is cut in half with each card added. SLI must be in matching pairs (both cards must be the same) while Crossfire can be mismatched provided they're of the HD 3000 series or higher. The cards are connected to each other via an internal ribbon cable.
SLI/Crossfire is good for both mid-budget and high budget gamers. Mid-budget gamers can take a cheaper card and add a second one at a later date to boost performance. High budget gamers can add two or more top of the line cards to get the ultimate in performance.
In addition, some cards are labled "X2" such as the Radeon HD 3870 X2. These cards have two GPUs on a single card, which allows people without proper SLI/Crossfire capable systems to gain the full benefits of dual GPUs. Furthermore, two "X2" cards can also be put in standard dual PCIe slot SLI/Crossfire systems for a four GPU setup.

Power Consumption
As I mentioned before, higher end cards use more power than lower end ones. Before buying a card, you'll need to make sure your computer's power supply is up to the job. I recommend a minimin of a 450w power supply for gaming, which should be fine for most systems. Enthusiast cards may require a 500w power supply. You'll need a minimum 600w one if you intend to run SLI or Crossfire. Most higher end cards today need to get power directly from the PSU. Your power supply will need at least one six pin "PCIe" connector. If your power supply doesn't have one, you can buy adapters which convert two 4-pin "molex" connectors into one six pin PCIe connector. The 12v rail on your PSU should measure at least 18 amps as indicated on the side of the unit. If using the molex-PCIe adapter method, the card should ideally be on it's on dedicated line if possible.

Size
You may want to measure your case to make sure the card fits, as some newer ones can be a tight squeeze even in common mid-tower designs. Low profile cards are available for TV top HTPC systems, which have smaller cases.