It depends a lot on what kind of game you are making, or rather, what kind of art you need.
But regardless, don't get bogged down by the art. If your game is fun to play with "programmer art" (aka "placeholder art") you can then spend time on the graphics -- either doing it yourself, buying pre-made art, hiring someone to do it or getting volunteers who want to be involved with your project (which is a lot easier to do when you have a finished except for the art project.)
If you spend a lot of time on graphics before you have a game that is fun to play, you may totally waste that time because you may discard the game. (Unfortunately, I learned this the hard way. Several times.)
Okay, I've said my piece. Now here are some excellent resources for learning to make 2D game art.
Chris Hildenbrand's 2D Game Art For Programmers Tutorials on Gamasutra
AWESOME! Uses free tools and assumes you know how to do basic things, like make circles and gradients. Not step by step, but enough if you have any idea of how to use the tools. Concepts applicable to Illustrator/Photoshop too. Don't miss the link to part 2!
Chris Hildenbrand's 2D Game Art For Programmer's Blogspot
EVEN MORE AWESOME! Continues on where the original Gamasutra tutorials left off. In fact, if you go back to the earliest posts, you'll find the Gamasutra tutorials. Chris also has some assets for sale here--eg., his Block Buddy packs of animated characters. "Life is too short to make bad art."
Creating 3D Sprites and Using Them In Construct 2
Short tutorial by Construct 2 user Martin on using Google Sketchup to make buildings for game scenes. If you like this approach, there are tons of resources out there for how to use Sketchup.
(Alternatively, you can use other 3D tools like Daz Studio and Bryce, which are currently available for FREE at daz3d.com to render 3D models into royalty free 2D game art. Lots of tutorials for using them, too. Lots of models for purchase at daz, renderosity.com, etc.)
insertcode.co.uk 2D Game Art Tutorials
This is a new blog (started at the end of January.) So far there are eight tutorials on using illustrator and photoshop to create game art.
Igor Sinkovec's Walking and Running Animation Tutorials
Short lesson on animation theory.
That's all for now. As I remember or come across others, I'll post. Hope it helps!
EDIT: As promised, I'm adding more tutorials as I find them. Just one to start, but there will be more, I promise.
More Tutorials
==============
Pixel Art Tutorials
These are by Scirra community member Noise. So far there are 8 or so, but it looks like a great series on pixel art. I found the lessons on color, contrast and light very helpful.