First, ensure that you have not overclocked your card. If you have (or aren't sure), set everything back to defaults and slowly work your way back upward, if you want to try overclocking, again. Be sure to make a note of any changes you have made, recently, as this could be the cause of the problem.
If that doesn't work, you may have a problem with the thermal paste (or lack thereof) between the chip and heat sink. Make sure you have some high-quality thermal paste that is still reasonably new (not dried out). I like Arctic Silver, but there are other good brands out there.
Turn the machine off and let it cool down. Remove the heat sink and carefully clean off all the existing thermal paste. Apply a small amount of high-quality thermal paste in the center of the chip, put the heat sink into position, and press down gently. Secure the heat sink with screws, clips, or whatever method it uses. If you see thermal paste coming out the sides, you put too much on. Remove it all and try again. Make sure that no thermal paste touches any exposed circuits. What you want is barely enough thermal paste to create a circle that extends to nearly the edge of the chip, but doesn't go over the edge. Some people like to spread it with their finger to evenly cover the chip in a thin layer, and a good case can be made for that method, as well. Make sure the fan on the heat sink is plugged into the correct place, so that its speed will be regulated properly.
You may need to do a firmware or driver upgrade or downgrade. If the firmware on your card has a bug in it, that can result in incorrect temperature reporting, poor fan speed management, overheating as a result of inefficient algorithms, and other issues. The same goes for drivers. If you have recently upgraded your drivers or firmware, that could be the problem; try switching back to the version you were using before the problem started. If you are not using the latest (stable) drivers/firmware, you might want to try upgrading to the new version. Try fixing driver problems, first, though, since firmware changes can break your card if they go wrong.
It's possible that the fan has developed a problem. Perhaps one of the blades got damaged, and isn't moving air properly. Perhaps a bearing is worn out, causing too much friction, and reducing speed. If you have any reason to suspect that the fan is on its last legs, replace it.
In rare cases, if a chip gets too hot, it can start to warp the metal of the heat sink, especially if heat is not being distributed to it, evenly (such as when thermal paste is not applied properly). If this is the case, you may see a tiny bit of "waviness" on the heat sink when you pull it off; or you may not, since even a microscopic variance can cause problems with heat transfer. If you suspect this to be the case, buy a new heat sink that gets good reviews for the card you're using (not just any card!), or use the stock heat sink that came with the card. Unless you're overclocking, the stock heat sink is often quite good on most cards, and is guaranteed to fit properly--which is more important than any advanced features an after-market heat sink might have.
Finally, are you playing a new game or running a new program? It could be that what you're doing, now, is just more GPU-intensive than what you were doing, before. Newer games/graphics programs or more intense graphical settings in those games/programs will make your GPU work harder, increasing temperature. If this becomes a problem, try reducing the settings. If you find that you just can't play the new games or use the new programs that you want to, it might be time for a new video card.