Applying thermal paste is a wildcard - it can work well, not at all, or make things worse. Nor is there one perfect method to apply the paste. Each heat sink is different in terms of quality, how flat the surface is, etc (if that makes any sense), so more paste may be needed for your particular setup. Also make sure you're lining up the screws to the screw holes on the heatsink exactly (there is some room for error there, so the heatsink doesn't line up exactly, just be careful).
Personally I've repasted my rMBP 3 times. The first time I used a vertical line for the CPU and a grain of rice for the GPU, and let the pressure from the heatsink spread the paste. I saw an overall drop of about 5 degrees C, idle to load. In retrospect I should have been happy with that, but stupid me was unhappy, I wanted better results. So the second time I took the time to tint the heat sink and spread another thin layer with a credit card. My idle temps (rMBP in sig) were high 30s C, and I was happy - until load happened, then I'd temporarily shoot into the 100s playing flash games in Safari, which is completely unacceptable. So the third and current time I went back to the line method and I'm back to where I was initially. I'm idling now in the low 40s, and load high 80s, occasionally hitting low 90s. I see 100s in stress tests, but that's about it.
So I'm done with pasting for now. But ultimately there is no one perfect way of doing it.
Also, just another word of caution (kind of off-topic, but nonetheless). One of the reasons I repasted in the first place is because I thought the CPU was throttling in games due to high temps. Skyrim in particular was a pain in the a** because I'd micro-stutter all over the place. After doing some more reading I've discovered some alternate theories as to why the MacBook throttles. This is a good discussion:
http://forums.anandtech.com/showthread.php?p=35325843
The short of it is if you notice you're dropping frames in games, you might want to try reducing the load on the power supply. For example, once I stopped using my huge external monitor and removed my external HDD and 4 devices from my USB hub, my gaming performance actually improved quite a bit, and my Skyrim problems went away.
Just something to chew on.