I also assume that I should use a Linux distribution in order to do this properly. I have a Linux machine already. So I guess this will do.
Can anyone suggest a way to get started with this?
Since you already have a Linux machine, you could go with that and install PHP/MySQL/phpMyAdmin or a LAMP package (I assume the machine already has Apache installed by default). There are a few issues there that I will not muddy the waters with now. I am assuming you know how to do the networking to the Linux machine.
You could also download a package like XAMPP and install that and have a reasonable facsimile of a PHP-Apache setup. Or, you could download a virtualization package like VirtualBox, install Linux and PHP on it, and have everything on the same computer with a more genuine Linux setup than XAMPP may allow. (Not something most people will need to be concerned with.)
i would suggest setting up your staging server under a different subdomain (e.g. staging.example.com vs www.example.com) using the same hosting/isp environment.
That is another possibility. However, with things like Wordpress or anything that has URLs hard coded, using a subdomain is a pain in the butt later. You can use your computer's hosts file to resolve the DNS to your development machine and just use your regular domain name in the web server's virtual hosts file.
I have found that when doing development that mimicking the setup of your production machine is best. That is, making sure the PHP and Apache version you are developing on is the same as your production web server and also using the main domain. That way, the final testing and debugging is minimal.
It all depends on which way the original poster wants to go. I like to keep everything on the same machine as I find it easiest.