There are a lot of kegging resources out there, so I decided to not recreate the wheel and go through the whole deal here. I started to, but then it turned into a novella. Instead, I'll just toss in my $0.02 and link to some resources. Maybe I'll expand on it down the road.
When I first got into kegging, I bought a few kegs fully reconditioned. What this means is they were fully cleaned and had the o-rings replaced. They were nice and clean and ready to go. They also cost over twice as much as plain used kegs. Generally, used kegs are just tested for pressure, maybe if you're lucky power washed. While prices have jumped over the years, there is still some good money to be saved by buying used, un-reconditioned corny kegs.
Before you can get going, you'll need some tools. You'll likely need both a 7/8 and 11/16 deep socket wrench. The key is the deep sockets, as most kits won't be big enough. Look for something that will work with spark plugs. There are two sizes of posts out there, most seem to take the 7/8, but I've got a few kegs that need the 11/16. You might be able to get by with the 7/8.
Also, just for the sake of it, I'll mention that there are two types of kegs, ball lock, which are the Pepsi brand kegs, and pin lock, which are the Coke. The ball locks are by far the most common, so I'd recommend staying away from the pin locks. Not a big deal, but no point in having two sets of everything or having to really hunt for deals on pin lock kegs.
To recondition a keg, basically you're pulling everything apart, cleaning well and replacing the rubber. Whenever I clean my kegs, I pull everything apart anyway, so the only difference for me here is the replacing part. The rubber has 5 o-rings, one big one for the lid, two for liquid and gas tubes, and two for the posts. The best place I found for the o-rings is McMaster-Carr. For $20 or so w/ shipping, you can practically have a lifetime supply of o-rings, with exception to the lid, which run you about $2 each. Here are the part numbers:
Dip Tubes (100) - 9452K172 BunaN #109
Posts (100) - 9452K23 BunaN #111
Lids (10) - 9452K218 BunaN #417
The second area is the poppets. This is optional, but I've decided it's a really good idea. Once you empty a CO2 tank or a keg of beer (on the floor), the idea of replacing poppets won't sound so bad. 
They're getting expensive too, unfortunately. When I first replaced a batch, they were $2.50 each, now they seem to be $4.25. I don't have a bulk source for these, so if anyone has one, I would love to hear it. I get my poppets from Northern Brewer (#K102). That poppet seems the most universal. I've replaced all my poppets and that one works well in all of them.
The idea with the poppets is the poppet get old, and sometimes stick. It seems also that not all of them really fit well. Keep in mind, these kegs have seen many, many miles and much abuse. When the poppets stick, they will slowly leak after removing the quick disconnect. Or, it will have a high-pressure leak and spray you in the face. Either way, it's not a whole lot of fun. Between the o-rings and poppets, you'll be pushing $11 for each keg. Kind of sucks with the rising costs of kegs, but the alternative makes it worth it. Even if it makes your reconditioned keg as or even more expensive as buying it reconditioned, you'll do a better job and have a better functioning keg. Since I've replaced them, I haven't had any problems with sticking or leaks.
The last area is the OPRV (over pressure relief valve) in the lid. I have three different types of these valves, and the oldest one goes on a unique lid. I've got a separate post in mind for replacing the rubber in the valves. It works for most valves, but not all. You could also replace the whole valve, if you wish, but that's pretty expensive -- stay tuned.
Going back to the cleaning part, it's perhaps a little excessive to break the keg down completely and clean, but I've often had gunk built up in the posts. I also fill the keg with hot water and cleaner, and let it soak over night or so. Then I scrub it out with a soft scrubby, and a clean (and dedicated!) toilet brush for the bottom. I just think it's a good idea to spend a few minutes to get in there and make sure everything is really clean. 5 minutes is nothing compared to the time wasted on a spoiled batch.
Lastly, I'm a fan of the spray keg lube. The spray stuff is real easy to work with and ensure a good seal. I also spray some up into the poppets after cleaning, just so nothing sticks, but that's probably not necessary. The lube is particularly helpful on the keg lids, which can be a little tricky to seal. The lube is food-grade silicone, so it's sanitary and safe.
So, there we go. My tips on quick and easy keg cleaning/reconditioning/maintenance.
And some references:
Comment feed for this post
For poppet valves (and used kegs and parts), check out Brewers Discount - they current list poppets for $2.50 - http://web.iwebcenters.com/brewersdiscount/productCat15956.ctlg
Thanks!
-Dick
Completely forgot about that one. That's why I hate calling my shot. :)
I dug up the info on the stuff, so I hope to get the time to hammer something out shortly.
Richard: Depends what your kegs look like. If you just have dirt and goop on it, try Bar Keeper's Friend and a scrubby. If you want to polish them up, get a sander buffer and lots of sandpaper. Go with a course grit to get the scratches out, then a few finer grits to polish it up.
I did this on one keg and it seemed to be a ton of work and messy. I eventually figured out the beer doesn't touch the outside of the keg and this doesn't make the beer better. :)