I'm a photographer, really, but I still know a few things about imaging. I think the best way to start is to look around you at designs in nature, in your house, and everywhere you go. Think about how things fit together in the world and then think about other works you've seen on the computer. Then experiment and see what you come up with. Reading tutorial after tutorial is incredibly boring and mostly pointless.
As for a program, I've used just about everything at one point or another. For normal stuff, I use Photoshop (and it's cousin Lightroom for photography), but I've also used the GIMP (clunky user interface should be cleaned up this next version or two, but it doesn't offer the same level of documentation, extensibility, ease of use, or quite all of the features of Photoshop), Paint.NET (which is Amazing at what it does, but still slightly limited as to the scope of what it does, and a few other things not even worth mentioning. If you want to spend money or engage in illegal activities, go for Photoshop. Otherwise I recommend Paint.NET first and then the GIMP second.
watch some online tutorials, search photoshop tutorials on google, that is a good way to learn stuff. pixelperfect is a web site that has a bunch of tutorials, and once you find a good site that you like, watch all the videos on that site. Make SURE you try out the techniques yourself or you will not truely learn them.
hope this hleps!