I guess that’s something that most people here have problems with.
I consider myself being not that bad with making graphics and am currently writing some tutorials for Corona Users on what they should consider when making GFX and how to make good looking stuff 
My blog isn’t up yet, but you might follow my twitter to see if there are any news about it (#xxxfanta).
Now to your question about programs and resources:
I’ve always been using the Adobe CreativeSuite, including Photoshop and Illustrator , for designing, that’s why I can’t tell you much about free software.
I know that many people use GIMP as free alternative for Bitmap graphics and Inkscape for Vector graphics, but can’t tell you much about it.
The type of program you want to learn depends on the look of your game.
How should it look like? Clean? 8Bit-like? Textured?
I hope to get my blog running soon, so I can write some tutorials for this 
Besides that, I found out that
iNSERT.CODE is now publishing tutorials on his new blog:
http://insertcode.co.uk/
You should check it out - it should be very useful for you! 
Last but not least: Designing is a long-term process and you need to be patient 
Good luck with that!
Chris [import]uid: 13097 topic_id: 21542 reply_id: 85313[/import]