On the HowToForge website, there's a new step-by-step tutorial on getting a complete setup of Linux, EngineX, MySQL and PHP on a Ubuntu/Debian box working.

This HowTo will describe the setup of an efficient http server and mail server for small or medium configurations (as low as 96 mb). So this config is ideal for a small VPS. You can find a good choice of cheap and performant VPS (XEN) at x|encon, a german hosting company. they provide many scalable VPS solutions with pre-installed Debian and Ubuntu disc images.

They have it broken out into five overarching steps for getting things working, but there's lots of little sub-steps you'll need to work through to get it up and running. Thankfully, most of the hard part (installing the packages) is handled through the apt-get command and you won't be required to compile.