I have to set up a new LAMP server for different clients here and there, but not with enough frequency to warrant using a particular scripted solution or 'stack' from a particular hosting company. Plus, I like to have a portable solution that is flexible to the needs (and constraints) of a client's website.
Note on hosting providers: For hosting, I've used a very wide variety of hosts. I typically use and recommend Hot Drupal VPSes or Linode VPSes [affiliate link] running CentOS for a good LAMP server. Shared servers are only good for nonessential or low-traffic sites, but they are a bit cheaper and easier to use for simpler needs!
So, here's a typical step-by-step process for how I set up a CentOS 6 (similar process for CentOS 5) server for LAMP (Linux, Apache, MySQL, and PHP), often for low-to-moderate Drupal sites (one or many):