Depends on how much you want to spend on the video card. I always get one in the $100ish range and just upgrade later, rather than buy something freakishly expensive. All of my builds have been under $500, and although none of them were really planned from the start to be a gaming PC, they each filled that role well enough in their own time. My current rig is approaching three years old and may not be able to run Skyrim without reduced settings, though it's run everything else I've thrown at it just fine. I've upgraded the video card once.
The key components for running a game are CPU and video card. I sincerely doubt Skyrim will be akin to Far Cry, Crysis, etc in that only the gaming elite'll be able to run it well, that just doesn't seem like something Bethesda would do. It took them this long to ditch Gamebryo, for cryin' out loud.
CPU shopping isn't all that hard, the prices are generally pretty closely related to actual performance and it's pretty easy to research and pick out the best bang for the buck--if that's what you're going for. You can save a bunch of money here by finding CPU+Mobo combo deals (definitely absolutely check Fry's Electronics, if you have one in your area). Generally, AMD will provide the most bang for the buck. CPU prices trend steadily downward and you may save money by waiting.
Video cards are a whole different can o' worms. You're liable to spend 50-100$ more for each marginal improvement. It takes a lot more research to find the best one for your budget. Since you're just starting out it's a little easier since you don't have to compare it to your existing card and say, "is this extra performance worth this much money?" That's the truly annoying part. I recommend doing your video card shopping online at NewEgg or something. Physical stores simply don't have a big enough selection. Prices on GPUs don't drop as easily as CPUs do. Waiting may or may not save you money.
There's no rule of thumb here. I've purchased and had both good and bad experiences with both ATI and Nvidia. Neither is better than the other
in general. Keep that in mind.
RAM is a secondary concern and I've never been a big believer in premium memory. More trouble than it's worth IMO. Just find a good deal on 4GB or more. Preferably more, but perhaps not too much -- Free memory is wasted memory. If I were building a system today I'd probably put in 6, but no more than 8. I have 4 currently and rarely even use 3.
Long story short I'm betting you can build a computer today for around 500$ and still run Skyrim just fine. If you want to run it on absolute highest settings, be prepared to spend double if not triple that--the video card alone will likely be 400-500 bucks!
Like I said, I'm a budget builder, I go for the best price

erformance ratio I can. If you want to invest more heavily in your CPU or GPU, go right ahead--that's easy.