It has been my experience that 90% of laptop overheating issues are caused by dust clogging the air ducts leading to and around the cooling fan.
In all the laptops I have worked on, the procedure for cleaning the fan has involved extensive dis-assembly to get to the fan and the air ducts. Although each laptop is somewhat different, the dis-assembly procedures seem to be remarkably similar, so here is a generic set of instructions for taking apart laptops and cleaning the fan.
1) It has usually been necessary to remove all the easily removable components on the back of the laptop: the battery, cd drive, ram, hard disk- generally all of the stuff you can get to from the back of the unit. I then usually remove all the screws visible from the rear- some of them are hidden under things like the hard drive, etc. Sometimes the screws will be hidden under the adhesive round rubber "feet" the laptop sits on. Sometimes, too, you will find a screw hidden under a sticker. If you push on the stickers with the rounded, plastic handle of a screwdriver, you may find an indentation... a telltale sign that a screw is hidden there.
2)After you have removed all the screws and components you can access from the bottom of the laptop, turn it right side up again. You may have to remove the little panel right above the keyboard, which houses some buttons and lights, usually the power button and other similar buttons. That part is usually snapped in, and possibly screwed in from the rear. Most laptop parts require some force and prying to come apart... but never too much. If you feel the need to pry too hard, check for some screws that you missed, or check to see if you can take another component off first.
3)The keyboard usually needs to be removed next in order to access more screws which will be hidden under it, which hold the top of the laptop case to the bottom.Be careful removing the ribbon cable to the keyboard.
The goal is pull the laptop apart (pulling apart the upper and lower portions of the case).You will almost definitely have to do all the things mentioned above, as well as take off some other bezels, cables, screws and wires.
The motherboard may also need to be removed, involving more screws and ribbon cables. Be careful not to bend it too much. Sometimes a heat sink will have to be removed from the CPU, in order to get to the fan or the compartments where air travels. If that is necessary, make sure to have some heat sink grease around in order to put the heat sink back on... the grease is really important. .
One thing I have noticed is that it is always better to mark and remove all those slender ribbon cables you encounter while you are going in there. Snap a photo or two before you remove them, and use a sharpie to mark where to put them back. It is always better to remove them, rather than leaving a component dangling around connected only with a ribbon cable. If you do that, you will accidentally move the component too far and bust the ribbon cable or the connector, and then you will have a much bigger project on your hands!
In short, extreme care should also be taken in dis-assembly, because those cable break easily. You will most likely have to take all types of things apart in order to get to the fan.
Once you clean the fan and are ready to assemble the unit, make sure you connect all the ribbon cables as you reassemble the unit. Go slowly.
Additionally, if you removed the heat sink screws, be sure to tighten them in the
proper order... so that it seats flush on top of the CPU. If the order is not marked numerically on the heat sink, at least try to stagger the screws so that all the screws you tighten are far apart from one another.
When screwing in circuit boards and components, make sure you don't put screws in until you have reached the right point at which to do so. Some screws are made to go through several boards, so you don't want to put them in until you have all the boards assembled. If you put the screw in too early, you will wind up in the end looking at a screw hole with a screw head buried inside of it, and will have to backtrack...or just pretend you didn't see it.
Here are a few photos of the most recent laptop I have disassembled and cleaned. The overheating issues were fixed, and the unit ran much cooler once the dust was removed from the fan duct and cooling fins.