First thing to do is get a Giottos Rocket Blower and do a dry cleaning. This will get most of what's on there. I've only had to wet-clean the sensor on any of my cameras a total of twice in all my years of shooting.
If that doesn't work, I like the Copper Hill Method: http://www.copperhillimages.com/?pr=Tutorials2
If you do a wet cleaning like the one above, my best advice is to be conservative. It's easy to get too aggressive and scratch something by accident. So take your time, be careful, and breathe deeply. You know: measure twice, cut once.