Download Appserv (Google it). It is an open source WAMP. WAMP means Windows Apache MySQL PHP. It installs all of these things at once and configures them to work. Basically, it installs a web server with PHP and MySQL support on your PC so you can mess around with PHP without having to upload to a webhost (because as you may know, a normal browser without a web server (such as Apache) can not parse PHP).
After that, I recommend getting a book. I learned PHP with one book, called "PHP For The World Wide Web second edition" by Larry Ullman, from the Peachpit Press. It's a pretty good book. There are better books I'm sure, but it covers pretty much all the basics and some intermediate stuff. The only thing it didn't cover (which disappointed me) is the object side of PHP.
Anyway, get a good book and check out some online tutorials. One of the best ways to learn is to download scripts that you want to write and study them and figure out how they work, then write your own. It takes a while to learn, just be patient.