It does come with thermal grease but I recommend buying some Artic Silver 5. It should cool your CPU to around 27C and 34-36C full load.
that TOTALLY depends on voltage applied to your cpu.
i have never been able to make my cpu load 100% and stay below 40*. ever. below 50* is doing good.
maybe if my room was really really cold, but its not.
ALSO:
36* idle is not bad for that cpu. its not as good as it could be, granted. but unless you jack the voltage up to like 1.75 or something dumb(i think the stock on a 3500 is 1.4, if its s939) it aint gonna jump 25*C at idle. it may get to 60* loaded. maybe. as long as your idle temp is under 38-40 you have a little room to play with it.
dont increase the voltage AT ALL at first, see what it will do on stock voltage. that way, you dont have to worry about heat at all unless you have a load temp over about 60. it will take more than that, but to be safe keep it below that until you know what you are doing.
you will learn fast, dont worry. another thing to not worry about is screwing up your cpu. the only way you can do that is by hosing up the voltage. usually, if you screw up your rig wont start, and you can reset the cmos and start all over again (a joy).
P.S. it helps most of us out here if you do a little reading or googling and kinda get the basic principles down. that way, we can be more concise in helping you achieve a good overclock.