Hey Matthew,
All of the above are great ideas, and they all can help you get under way. What I suggest though, is that a lot of these major companies provide 30day free trial offers. Take advantage of that, use all the programs see what one your most comfortable with and then, you can have a better idea of what to look for. Just like anything, everyone has a special product or tool that they like over another. Research is the key. That's why I highly recommend using the free trial offers.
After you have found what program you like the best, as with anything shop around for the lowest price. My first stop is usually softwareoutlet.com. They usually have all the programs that are used for graphics to give you all the effects for skinning. Then, I'll pop over to Amazon.com and compare to Ebay to see where the cheapest is. I have bought many things off both places and haven't really had a problem yet. One, thing Ebay is doing right now to be aware of though, is ppl are selling a major software program for dirt cheap, but they're not sending the install disk, they e-mail you with the serial number; telling you to download the trial version and then, they use the serial number during the install process. As with anything be careful, read fully what you are buying. I just purchased the Corel Graphics Suite12 through E-bay, got a really good price and it came with all disk in the box, brand new--alot cheaper than buying through the company or store. Also, Photoshop Elements 4.0 is on softwareoutlet.com for less than 60.00. It's a pretty good program and you can do just about all the same things as PhotoshopCs.
Then, once you get the program you like the best you can search for tutoriols for that program, which would take less time than, searching all through the tutorials.
Again, it's all in your preference. Hope this helps...