Quoted from flecom:that depends on the tools being used... if you are using braid then yes, flux is almost mandatory... if you are a using a nice de-soldering station with a pump it is unnecessary
Completely depends on the board you're looking at and what condition it's in.
A board where the solder is dull and not shiny often desolders 10x easier if you use a little liquid or paste flux. Resoldering the part before desoldering accomplishes about the same thing, but then you're heating the board up one more time.
Liquid flux is inexpensive, works well, and easily cleaned up. I'd rather be 'safe than sorry' in applications where the traces are fine and not forgiving - like a RAM chip on a WPC CPU.
Don't be afraid of flux, just make sure you clean it up when finished.