OT:
I have a 2600k (obviously not a 2500k but in the same vain).
I have a Noctua DH-14 cooler and have my CPU OC'd to 4.3GHz.
I get around 25-30 degrees idle and about 50-55 when under full load.
Overclocking is very simple - if you're not sure what you're doing just look up a guide for your mobo/CPU and follow it.
Truthfully, the hardest part is probably installing the cooler as it can be a bit of a pain in the ass and fiddly.
tl;dr
I would highly suggest OC'ing the 2500/2600k but yes, you will need an aftermarket cooler if you're going in to 4.xGHz region.
Posted on Tuesday, 6th September 2011