I only know how to overclock Athlon/durons.. no experience with intels.. This is what I would do though.. look at your motherboard manual (i hope you have this) and check inside to find if there are any dip switches or jumpers on the motherboard that control the fsb.. if there are.. play with em.. up your fsb.. I'm pretty sure that's how you overclock a celery.. other than that, you might want to type your motherboard name and model into a search engine (right now I like google).. and see what you can come up with.. I hope this helps.. but yeah, look in the manual.. it won't outright say "TO OVERCLOCK DO THIS AND THAT"... but it might point you out to the jumpers/dip switches that will adjust the fsb..
about the heatsink thing.. check your temps now.. and go up in slow increments.. and keep testing it and checking the temps.. I think you can get a mild overclock with your stock heatsink.. I could with a hot athlon and a stock heatsink.. so yeah.. go slow.
I hear that people go from the stock 66 mhz of the celeron all the way to 100.. I don't know if all celerons will do this or not.. hopefully someone that has experience will reply too.