^+1 Agreed.
If the stuff is stuck firmly an old toothbrush is an ideal cleaning tool, AMD usually uses 4 Phillips screws to hold the fan to the heatsink, just unscrew it and you can get right into the fins to clean them out.
Don't know what you know so I'll drop some extra points:
Don't try to take the fan off with the cooler attached.
The cooler assembly is held down by a spring loaded clip, just push down on the little tab and unhook it from the plastic retention frame.
The P II uses many, many tiny metal pins to make contact with the motherboard, these are very easily damaged and due to their small size very, very difficult the straighten so don't just try to pull the cooler off the CPU if it's stuck, push down gently, applying more pressure to one side than the other and twist.
Hard, dry thermal compound can sometimes be removed with the edge of a credit card, don't use anything hard and sharp, you'll damage the surface, if it's just a sticky goo plenty here use rubbing alcohol to get it off, but any high purity alcohol will usually shift it.
Try not to take the CPU out, use a coarse paper towel moistened with the cleaning fluid of choice and clean it in situ by wiping inwards towards the centre, these pin type parts can be a total bast*** to get back in.
Use a good quality thermal paste, there's plenty out there but in general the white silicone based ones are poor performers.
Apply the paste to the cooler only, you'll clearly see where it was contacting the CPU so apply a blob of paste about the size of a grain of rice and spread it out to form a fairly even film over that contact patch, most prefer to use a credit card for this.
Don't forget to reattach the fan wires to the motherboard...
No,really, you'd be surprised just how easy it is to do all the proceeding work with total precision only to forget to attach the wires.