Grab a can of compressed air and blow it in the fan vent (I suggest you go outside since it will likely be pretty clogged) to clear some of the gunk.
EDIT:
MarkM suggests blowing might cause dust obstruction. If you decide to open the laptop anyway, I wouldn't blow air and just clean the fan when it's out. However, I've never had issues with blowing air in the fans of numerous laptop and desktop system. Use common sense and follow the instructions on the can, which generally suggest you keep some distance from the target (that is, don't stick the spray can nozzle in the fan)
From an exact experience (with two different laptop models) it's also likely that the thermal paste at the CPU has thinned out. You should re-apply it (more isn't better, so follow instructions) and give it another shot.
I'd do both, and you should be in the clear if it's indeed an over-heating issue. But the compressed air might be enough, so if you're not comfortable re-applying paste, try installing after you clean up the fan.