I use a nice pair of Crescent miniature flush angled wire cutters. I usually cut the cap half way down, gently wiggle the remaining metal can and packing off of the two legs with a pair of small needle-nose pliers then break the plastic base in two to remove it. Now I have the two legs sticking up like Mk has which are a cinch to desolder with your soldering pencil. You'll get electrolyte oozing around so remember to clean up really well with alcohol when you're done. You'll probably also see some crusty stuff hiding under the plastic base that needs to be cleaned up too.

Once the crust and ooze is swabbed off, I clean the old solder from the pad with solder wick and re-tin it. A tiny bit of liquid flux down on the pads makes the new caps's leads flow right into the fresh pad. More cleaning to remove any extraneous flux and I'm done.

I don't know if this is a "correct" way or not but I'll be damed if it doesn't keep me from lifting pads and gives a nice, clean board when I'm done.