Your computer is definitely overheating. If it is a tower, it will be much easier to fix. The same principles apply for a notebook, but it is harder to get to everything, and usually require removing the motherboard. Obviously power down the computer before attempting anything below.
If you open the side of the tower you will see a 80mm fan on your motherboard. There should be a (usually silver) block of metal underneath it. This is your CPU fan and heatsink. All of the hold downs are different depending on what socket you have, but not matter what, you need to remove them both. You can remove them as one unit.
Underneath that is your CPU. You do not need to remove it, but you do need to clean the "goop" off of it with a lint-free cloth and some rubbing alcohol. That "goop" is called thermal paste, and is available at any local computer store or usually RadioShack. That will need to be reapplied. You just want to squeeze a pea-sized amount on top of the middle of your CPU before you put your heatsink and fan back on.
While you have your heatsink and fan removed, take it outside and blow it out with an air compressor or canned air. Remove as much dust as you can. Make sure your fan spins freely. If it doesn't, it will need to be replaced. Again - a local computer repair store or RadioShack. Usually it is only a couple of plastic tabs or four screws that hold the fan to the heatsink.
Once you have done all that, put the heatsink and fan back on the CPU, tighten down the hold downs, plug the fan back in, and you should be set to go!