After doing plenty of research and asking some electrical engineers who use them, I've found some points that were helpful in deciding.
Benchtop desoldering or rework stations tend to have the most accurate temperature controls, best thermal recovery, and extra features like programmable timing and hot-air, etc.
For example, if you plan to remove surface mount IC's on a regular basis, a hot-air rework unit may be ideal. They have nozzles for just about every IC package, and the higher end units can be programmed to pre-heat for a specific number of seconds, then heat for a number of seconds, and some have a vacuum nozzle to pick up the now-free part. (For example, see the Hakko FR-803B, a $1300 unit.) You have to weigh the cost heavily with the amount of desoldering or repair work you expect to do. For the occasional removal of parts, on a hobby level, this is likely overkill.
If you're just looking for a step up (or two) from the soldering iron and vacuum pump or solder braid, self-contained desoldering guns like the Hakko 808 can be found for about $200. While it has less fine control over temperature than a bench unit, it does have several benefits: self-contained vacuum pump, replaceable filters, and highly portable. Unless you have specific requirements for performing repair work, it will probably handle any through-hole work.
There are many online videos and tutorials about surface-mount desoldering. It is more tricky than through-hole for a variety of reasons. If you have to desolder SMT, you will want to check some of them out first. Some irons have tips specifically designed for multi-pin SMD packages, there are also hot tweezers and of course the aforementioned hot-air rework systems.
To recap, here are some solutions for desoldering through-hole and their relative price ranges:
The old desoldering pump, for about $15-20. Works "ok" but requires both hands and sometimes creative angles.
$12 at Radio Shack, requires one-and-a-half hands. I've not used one, so I'm not sure if it would be more or less convenient than a separate iron and pump.
Between $50 and $200. I found some for $50-100 online, but I have actually tried a Hakko 808 and can attest to the performance. Great for through-hole.
$400 and up. Lots of brands to choose from, Metcal, OKI, Hakko, Weller, etc. Once you start looking at stations, a variety of features and use-case scenarios start to emerge. Definitely geared more for commercial and industry use where soldering rework is an everyday occurrence.
One important thing to look for in soldering or desoldering equipment is the availability and price of consumables. Filters, tips and nozzles. They will need replacement. If you find an off-brand version, can you find parts for it later? If you get a quality station for cheap, do the replacement parts cost a fortune? Can they only be ordered from a foreign country?
Many manufacturers provide documentation and videos of desoldering equipment. Take some time to go through them, realistically evaluate what you will use (and what you can afford).
When I started looking, I thought I wanted a dual-port station (one solder, one desolder). Such stations are about $600. I probably am not going to desolder daily. I went instead with a single-port soldering station for $300, and a desoldering gun for $200. For my shop, the portability of the desoldering gun is worth the $100 saved and then some.
First of all: modern PCBs use lead-free solder. It has a higher melting point and a different "look" when solid. Sometimes it helps to apply a little bit of lead solder to get a better heat transfer between the soldering iron and the solder joint. After the whole soldering joint is molten, I use a vacuum plunger ("solder sucker") to remove bigger amounts of solder. Remove the soldering iron to avoid overheating the component.
Then (the component wire is still in the hole) I use some quality brand desoldering wick: I place the desoldering wick in such a way that it has a good contact to the solder joint, and then press on top of the wick. This way the wick has a good contact to the solder joint.
About heating up the capacitor: It may well be that you overheated the cap, I'm not sure if the metal case is has a good thermal coupling to the contacts.
Best Answer
In my experience, a soldering gun is typically a higher wattage device which is useful for soldering wire-to-wire or large, clunky components where you need a fairly large heat reservoir. The soldering gun I have is Radio Shack 100 watt, and is excellent for when I need to solder some 14 AWG stranded wire to something, or even just tinning the end of it. (It's been replaced by a 150/230 watt version.)
For any through-hole or surface mount work, you definitely want a temperature-controlled soldering station. David Jones, on his EEVBlog, recommends the Hakko FX-888 for starters (and has a soldering tutorial showing it), though there are many other brands he recommends in a video blog about setting up your shop.
I used to use a 15/30 watt selectable Radio Shack soldering iron, and I was able to get a lot done with it for over a decade. However, once I got a Hakko FX-951 temperature-controlled soldering station, I can't believe I ever made do with the old RS iron.
Honestly if I knew then what I know now (a common phrase in EE, I find), I'd have picked up a $85 Hakko FX-888. Don't let the unusual blue-and-yellow case fool you; it's a solid unit. (Hakko indicates that a digital version of the FX-888 is coming in January 2013, so you might want to wait for that.)
You can also go with a Pace, Weller, JBC, Xytronic, Ersa... There's a lot to choose from. Temperature control will get you more consistent results, but as others indicate, is not as important on through-hole work.
One last point: The temp controlled stations tend to have a lighter, skinnier iron handle than the ones that plug into the wall directly. This to me is a major advantage in being able to work around and between components and have more control over a lightweight iron.