Start with the uber-basic:
Is it in a hot place? Move to a cooler place.
Is there room for air to flow UNDER the laptop? If it's sitting in a pillow or bed the answer is NO. Place it on a hard, flat surface.
Are you overclocked? If so, dial back your settings, preferably to factory standard. If you have no idea what overclocking is, you probably aren't, so don't worry.
Now that the basics are out of the way:
Dust buildup is probably your issue. Try blowing out the vents under and on the sides of he laptop. Dust builds up easily in computers and acts as an ever-thickening blanket. If it's really dirty or you don't think you're getting a good enough angle, CAREFULLY remove the bottom panels and/or cover of the laptop to get better access.
ALWAYS UNPLUG THE LAPTOP AND REMOVE THE BATTERY BEFORE OPENING IT. YOU RISK ELECTRIC SHOCK AND PERMANENT DAMAGE TO THE LAPTOP OTHERWISE! YOU HAVE BEEN WARNED!
Pay special attention to the cooling fans and heat sinks (the copper or aluminum plates with all the thin vanes on them), as they are the most likely to get gummed up by thick dust. Make sure they all spin easily. (They won't free spin, as the magnets in the motor inhibit free spinning.) Remember, dust is the enemy! Hunt it down and eradicate it! 9 times out of 10, this will fix overheating issues.
If cleaning it out doesn't work
Listen for a fan noise when the computer is running. Wait for a little bit since some fans don't turn on until the computer has warmed up a bit and actually needs the cooling. If the fan is NOT running after the laptop gets hot, things may be a bit more complicated:
First, check your bios settings.
Access the bios by tapping the del key (DO NOT HOLD THE KEY DOWN, AS THIS WILL CAUSE AN ERROR) as the computer starts. If you see a windows logo, you missed your chance. Restart the computer and begin tapping earlier. I usually start immediately after pressing the power button.
Once in the bios look around the menus until you find something related to fan control. Make sure it isn't off. If you don't mind the fan running all the time, turn it to it's highest setting. If you can't find it, it's possible it isn't there, as HPs are notorious for bioses that prevent the user from making many customizations.
DO NOT MODIFY ANY OTHER SETTINGS AS THAT CAN PREVENT YOUR COMPUTER FROM WORKING AT ALL IF YOU DON'T KNOW WHAT YOU'RE DOING!
If you hear the fan start working again, SUCCESS!
If that doesn't work:
Look around your system settings in the windows control panel for anything relating to fan control. Search functions work very well here. Make sure your fan settings are turned on. Again, you may not find any relevant settings, as fan controls are usually managed by third party (non-windows) software. If there's any kind of "performance suite" installed on your computer, I'd check there first.
If none of the above works
Grit your teeth and break out your NON-MAGNETIC (VERY IMPORTANT) mini-screwdriver set 'cuz it's time to pull the fan. Generally there will be several tiny screws that have to be removed to get to the fan. Take pictures with your phone or a camera as you remove each piece so that you can easily reference where everything goes. Grab a cereal bowl to put screws in, as they LOVE to jump off tables and roll under anything nearby. Now get to it. Everything should come apart easily. If you have to pull hard on something, you're doing it wrong.
Once the fan is out and unplugged, make sure it is perfectly clean. Rubbing Alcohol and q-tips work great along with that can of compressed air. If you want to, you can try to test it with a 9V battery. Or take it to a Radio Shack or other electronics store and see if they can test it for you. If they want to charge you money to do so, walk away. It's so simple it should be gratis. If it doesn't work, find a replacement and install it using the nifty picture guide you made with your camera earlier. (You did remember to do that, right?)
Finding a replacement ranges from the very easy to impossibly hard. Try asking at computer repair shops or electronics shops in your area (bring that burnt out fan with you so they can match it!) Failing that, begin the Googling. Heck, try going through HP! It WILL be more expensive, but the fan you order is more likely to be the correct one. You shouldn't have to pay more than $15.00. Fans are the cheapest part of any computer.
I had same issue and I fixed it this way:
1. I opened the computer and removed parts until I had removed the speaker bar. I stopped here because I didn't wanna break anything and the next step was to remove the display.
2. Cleaned the fan with compressed air bought for 10 $ because it has a long pipe so you can get into the fan. A lot of dust was removed!
3. Putted it all together again.
4. Now it works fantastic! Two years of dust is gone
all of the above are good answers however, the best and guarantee to work solution is by reducing the Maximum Processor State(Power Options-->Advance Power Settings-->Processor Power Management) setting between 80% to 95%. Play around with the percentage alittle to see which one suits you best.