I’ve had a heatsink on mine since long before I started running RetroPie but in a rather closed case with just the heatsink it could easily go above 70 degrees celsius. Now I’m using a wide open case with heatsinks and fan and it runs about 25 degrees cooler now.

This is what I’m using: http://www.ebay.com/itm/Enclosure-Case-Box-for-Raspberry-Pi-B-w-Cooling-Fan-and-heatsink-Kit-NEW-/291186439319

My overclocking is:
cpu 1100
core 550
sdram 550
gpu 275
overvolting 6

Important for overclocking is a good powersource (700mA is not enough, I’ve tried).

Also I believe cranking up the core clock may be what have the biggest effect. Overclocking the gpu probably have very little or no effect. I went from 250 to 275 just to make it half the core clock. It most likely makes no difference.

I have three Raspberrys and all three are stable at cpu=1000, core=500, sdram=500 and overvolting=6 if used with a good powersource. That’s without active cooling. Only the one I use for RetroPie has been taken it bit higher.

Here’s a script that you can use to monitor the temperature:
http://pastebin.com/qmfUVPun

Btw, here’s my overclocking settings from my Raspberry that runs Raspbmc:
arm_freq=1000
gpu_freq=250
core_freq=500
sdram_freq=500
over_voltage=6
force_turbo=0

I wouldn’t be surprised if your Raspberry can run with those settings too if you have a good enough powersource (1A or more).