I normally use a heat gun, they work great, but do practice on some junk boards first until you get the hang of doing it without frying the crap out of the board. On some particularly hairy ones I've used a combination of Chip Quik and a heat gun. That lets you use less heat and have less chance of removing nearby parts in the process or overcooking things while still being able to heat all the pins at once and reduce the risk of lifting pads. Just make sure you remove as much of the Chip Quik tainted solder as you can, or it ends up being tricky to solder the new part on. The solder stays molten for what seems like ages.