not very hard. Pop the side of the case, pop the heatsink off, swap the cpu, put some paste back on, then put it back together.
It apears to be 775. The best one appears to be a 3.8ghz prescott HT, SL8J7. I would put in a 3.6 Cedar Mill HT,SL9KD because they run cooler.
The spec sheet says it comes with 128mb ram, I hope you upgraded that yes?
If you play video games it has an agp slot, a 6800gt or ultra agp on ebay runs about 30-40 bucks. a HD 3850 agp is the best but much more expensive.
Edit: note from some research i did: Does not support core 2 duo or even pentium D(sadly), so Pentium 4 is best option.