I'm not really sure what you mean when you say your fan had paste on it already. That is odd. You need to take it off and clean it with cleaning alcohol. Thermal paste comes with a scraping took to remove the existing paste. Also the less paste you use the better. What you trying to do is get a nice thin conductive layer between the plates.
Every stock intel cooler has TIM on it already. Think that't what he means
I think Don Perfecto was referring to the thermal compound already applied to the contact point of the stock heatsink (not fan).
The best practice is to clean the surface of the processor and the heatsink before applying new thermal compound, but it is definitely not necessary, especially for a relatively low-power processor, such as your Celeron (51W). Isopropanol will suffice, as Turk Ace mentioned. Just make sure that you pick 90%+ Isopropanol, or make sure that you wait a few minutes for any excess moisture to dissolve before seating the CPU.