My iPhone 3GS locked up this afternoon for apparently no reason.  Lovely.  Here are the steps I took to repair this particular iPhone.  Your mileage may vary.

1. Hold down the power and home buttons for about 6-10 seconds.  The phone will reboot, if it works from that point, you’re done.  Congrats.
2. If not, try once more.
3. Boot up your computer and launch iTunes.  Make sure it’s up and running, not updating or anything before you start the next steps.
4. Plug the iPhone into your computer.
5. Press and hold the power and home buttons until it resets.
6. As soon as the phone resets, let go of the power button, but keep holding the home button.  Get a good grip, you’ll be holding it for 30 seconds or so.
7. Eventually your iPhone screen will change to the “plug into iTunes” logo.
8. Your computer will inform you that the phone is in recovery mode.  Follow the on-screen directions.

What will end up happening is that iTunes will wipe your phone, reinstall the OS and firmware, and then sync all your info.  This will take a while.  You’ll lose any photos, gamesaves, etc, that occurred since your last sync.  So… make sure you sync often.