Laptops can be prone to overheating problems but this is usually cause by a build up of dust and dirt around the cooing sustem for the CPU. A message like this coming up as soon as you boot your computer could be caused by a faulty fan.
As a first step I would listen to hear if the fan starts running. If it isn't, then I would check the fan and its power connection - make sure it is fully plugged in. It is also possible that a build up of dirt on the fan blades would reduce its efficiency dramatically.
The reccomended method of cleaning out the cooling system is to use a can of compressed air, but use something - screw driver, paper clip, finger tip - to stop the fan spinning while you blow the air through it. Letting it spin can generate voltages / current that can do damage. A vacumn cleaner situated at the exhaust end of the cooling system will help to pull dust and dirt out as well
I have an elderly Toshiba beside me and on this one, to get at the fan you have to take the complete back panel off. Yours may have been re-designed with a detachable cover plate over the fan. If not, just be careful that the screws go back in the right holes !