Changing my CPU - how is it done?

[Demonheart]

So my sister's boyfriend brought me an Athlon 3600+ processor that he is certain will fit my motherboard, as I'm currently running a 2800+ of the same series. Now, the burning question is - how do I change it? I opened up my computer and there's some big freaking tower thingy on top of the CPU, I'm suspecting it's a fan. (called heatsink?) Must I just take that off and replace it with a new one? Also, I looked up some guides and they basically said I would have to use some paste to make it easier for the fan to cool the CPU. Is this necessary, for I sure as heck don't have any!

Oh, and one more thing. The CPU has like a plastic layer thing on it, am I supposed to remove it? It's a bit icky and won't come off that easily.