I overclock to the 1Ghz Turbo with this set of copper heatsinks installed:

http://www.ebay.com/itm/Raspberry-Pi-Heatsink-Set-100-Forged-Copper-/230955302367?pt=US_CPU_Fans_Heatsinks&hash=item35c6023ddf

They run way under spec for temps. I think they start downclocking around around 85C. If you're feeling like a "belt and suspenders" type setup they have the same set of copper heatsinks on eBay with a fan on the main SoC which actually does run even cooler yet. I find those heatsinks way overpriced (they say copper cools better than aluminum though) but they do have aluminum ones that are much more reasonable and probably more inline with what the cost should be.

Or they have cases with fans built right in the case but those require using a few of the GPIO pins for power and ground which may or may not matter depending on how you interface your controls (i.e. - GPIO vs Xin-Mo or IPAC, etc). You can use either a 3.3V or 5V pin with the premise being the 3.3V runs quieter but after trying both I can't hear either so I use 5V for the extra RPM's in cooling.

I have tried both and like both setups. If you use those taller copper heatsinks the smallest heatsink sits a bit higher than the other two (due to the chip underneath being mounted higher) and it doesn't clear the Adafruit case nor the PiBow (the only two cases I have used). I had to drill a hole in both to get the top in place. If you don't force the drill (patience) you can actually drill a nice clean hole through the Plexiglas type material and it looks decent.

I really like the PiBow case but they didn't take cooling into account at all. I think they treated it more like a cellphone chip and it's completely enclosed. The SoC does have holes/etching in the form of a raspberry above it and I drilled holes directly over the other two main chips with a 1/4" bit. If you didn't know what the original case looked like I don't think you would even take note of the extra holes as they blend nicely on the PiBow.

You could also just mount it open faced off to the side and not in a case (if you building a stick box or stand up arcade, etc.) which I found does make a difference also. They have mounting brackets for the Pi on eBay that work perfectly for this type of setup. I have a few and really like them.

With all that said some don't use any heat sinks at all and they run plenty cool with no issues. I think once your Pi is all setup in it's final build whether it's a stick case or cabinet, etc. I would do some "stress tests" (i.e. - play games ;) and watch the temps (there's commands and scripts to check) to see where they level off at and then decide if a cooling solution is warranted.

It seems to tolerate overclocking nicely but every time I overclock something a red flag goes up that I should implement cooling even if it's not needed.

The other thing is I always use the menu overclock (sudo raspi-config) so it doesn't void the warranty. Then go find that balanced cooling solution so it's not jumping between downclocking and overclocking or just go for overkill and know it's running plenty cool! :)