Newbie question: Do new Cpus need thermal paste?

YES! get paste on there ASAP!

You will need to put thermal paste on the CPU for the heat sink to work to its fullest potential you dont need alot just enough to ensure the CPU is making full contact with the heatsink. Some heatsinks have it pre applied if it was then you are fine but if you just replaced the CPU and using the old heat sink then you will have to clean the old paste off with some rubbing alcohol and a lint less cloth coffee filters work great. Then you will have to apply some thermal compound.

You can get compound for under $10 at Radio Shack

This should help you
http://www.techpowerup.com/printarticle.php?id=134

Well the reason I asked here is because there is some holiday in my country.. no computer shops open.. and both the Cpu and the heat sink are new
its a 3.2ghz amd phenom processor and stock heat sink that came with it

So should I wait until tomorrow to buy the thermal paste or just use it like it is now?

if you are using the stock cpu fan it sould have iton the end of it, if not go get some FAST

Look on the bottom of the heatsink. Grey thermal compound should be pre-applied already.

+1 It takes me 2 alcohol wipes to get it off so I can apply a brand I prefer.