On the NETTUTS.com website there's a new tutorial posted (by Tarek Farage) about creating your first custom Joomla template:

In this tutorial , you will learn about the basics of a Joomla template, and create one from scratch. We will quickly go through installing a local server and Joomla itself, and then create a basic functioning template.

The tutorial gives you a quick installation tutorial to get you up and running (if you're looking for a PHP installation guide, you'll need to find it elsewhere) with Joomla installed and working. He walks you through each step of the way - creating a simple template, installing it via the admin interface, and adding on more advanced features like layout features and modules.