Clean the vents first. It's the cheaper thing to do.
However, you must be careful when doing this using the normal compress (or canned) air. Compressed air cans will spin your fans more quickly than they were designed to spin. This can damage the bearings and motor on the fans.
Besides a quick blast (1 second or less at a time) to dislodge any dust, you'll need to actually open the laptop and hold the fan blades still while blowing the compressed air on them. This gets into "let the pros do it" pretty quickly.
Also, make sure you're running the laptop on a hard flat surface. Legs and cloth can block the vents. Make sure the room you're in is not too warm. Open a window, run a fan. These are further cheap things to try.
If after cleaning the entire air path inside the laptop and making sure the environment is conducive to effective cooling you still get the issues, try the laptop fan tray. The goal is to get as much airflow around the laptop as possible.
Laptops generally do not cool as well as desktops. That is why laptops generally run special components designed specially for low-heat and high-efficiency operation.
Some laptops, however, do worse than others. I bought my wife a laptop, the first tablet pc laptop from HP, powered by an AMD proc with discrete graphics. It developed numerous heat-caused problems and after finding out just how the HP warranty department worked and discovering I could cause the issues at will in a newly repaired laptop in less than a week, I was able to get them to replace it with a newer model which was much better cooled.
That is to say: There may come a point where you realize this laptop is simply not up to the task of running any intensive games. This is a sad realization, but it usually means you can also create the problems at will and if the system is still in warranty, you can cause the failures and get the system replaced, preferably with a different but comparable model which has better cooling.