I use 2 soldering irons to do it.  2 cheap $15 irons from Radio Shack and use them like tweezers.  Melt the solder on both sides of the contacts while pushing gently.  The cap will eventually slide off on its own.  You can add a little bit of solder to the pads first to speed things up.

For soldering caps, I use tantalum caps + solder paste.  A dab of solder paste on each pad, put the cap in the goop, then just heat the goop.  It melts and makes a perfect solder joint.  I suck at soldering, and I found it easy to do.