I use a soft paint brush to scrub the board and the fan blades of any stuck junk, and a can of can'ed air to blow the stuff away.
As to cleaning off the old thermal paste and renewing it. It depends on the age of the system. The older systems for sure, the newer unibody systems may not need it quite yet. In any case make sure you fully clean the old paste off and apply the new paste correctly. Don't over do it! You don't want a mess here and lastly, make sure you use a good paste (Artic Silver is what I use).