olanorig: I'm running Skyrim with my GF 9800GT. It runs great, no stuttering or glitches, even if you run the game with graphical enhancement mods. The video card by now is very cheap.
thebes: They are pretty cheap. Thought I would have to get one of the newest ones. At least the 545 or something. Thanks!
Bethesda is known for being brilliant programmers -- especially in the graphics department. You can get beautiful graphics on almost any gaming graphics card recently made -- and probably on non-gaming graphics cards.
Check PassMark for anything over a score of 325 to run Skyrim on low settings well.
You'll hit good medium-high settings around 1200 or so.
http://www.videocardbenchmark.net/gpu_list.php All that said, I'm assuming you have a decent system so that the graphics processor will be what slows it down. You'll want something with at least a bit of zip (not a Pentium III 350MHz powerhouse :D).
I'd recommend using this list:
http://www.videocardbenchmark.net/gpu_value.html to get the most bang for your bunck. For $66.99, you can get a GeForce GTS 450 and run that puppy on really good settings.
Side Note: Don't forget to have a power supply that can run the card, too.