Applying thermal paste is not that hard, there are different application methods depending on if the CPU has a heatspreader built on it or if the core is exposed.
If the core is exposed I suggest using this guide from Arctic Silver: http://www.arcticsilver.com/pdf/appmeth/int/ss/intel_app_method_surface_spread_v1.1.pdf
If the core has a heatspreader on it: http://www.arcticsilver.com/pdf/appmeth/int/vl/intel_app_method_vertical_line_v1.1.pdf
The application is the same on AMD CPUs.
And to answer your other question, yes it is really necessary to use thermal paste, with thermal paste you make sure there is contact between the two surfaces leading the heat to the heatsink. Without thermal paste you might experience very high temperatures which in the worst cases can lead to breakdowns and permanent CPU damage.
Also remember to thoroughly cleaning your CPU die, I recommend using 90%+ alcohol and clean all the old paste of it using q-tips or some pads.