I am planning to buy the g3258 (unlocked) and need a cooler to be able to keep it cool when o'cing @4.0ghz and above. My max budget would be around $40.
This cooler is worth it (I have an overclocked CPU on it right now) and it would be a good idea to add some case fans and to buy nice thermal compound: http://www.newegg.com/Product/Product.aspx?Item=9SIA6922R12413
http://www.newegg.com/Product/Product.aspx?Item=N82E16835103052
These fans aren't that great but are good versus the price. The more air being pulled through the radiator, the more the heat is being drawn away.
The better coolers will get you 7 - 10C more cool but will cost almost as much as the G3258, I wouldn't invest more than $30 ... and the best cooler that fits that niche is the 212.