OKAY, here is the procedure followed by pics.
1. Remove 3 screws from the base that holds the keyboard in place.
2. Remove the keyboard carefully. Unplug the keyboard cable.
3. Remove the 5 screws holding the heatsink/fan. (4 silvery + 1 black)
4. Remove the heatsink.
5. Carefully scrape off the old yellow, dried up and crusty thermal pad from the heatsink. A wide flathead screw driver does the job
6. Clean both the CPU and the heatsink with alcohol.
7. Use a "clean" eraser to remove the residual sticky stuff from both the cpu surface and the cpu. I used a Staedler eraser for the task.
8. Now, this step may or may not be necessary. There's a heat spreader on the top side of the heatsink fan. This piece of metal is very soft and I think it's pure silver.
9. Carefully remove the silver bar using a flat head screw driver. You will bend the bar during the process.
10. Clean the silicone based thermal compound from the bar and the groove that it fits in.
11. Apply Artic silver the CPU surface and the groove. You should really read up on applying artic silver on google. The key is not to use too much of it and spread it out evenly. I use a tiny plastic strip to apply the AS. As for the groove where the heat spreader fits, you don't have to be that careful.
12. Reassemble the heat spreader, heatsink/fan, keyboard.
13. Boot back up and enjoy.
So far from anectdotal experience, the bottom of the laptop takes longer to warm up and the temperature under heavy cpu load is noticebly lower. I have not used any programs to monitor the temperature; just my lap:)
Here are the pics, they might be in reverse order:

















