Art is just as coding: Practice enough, and you'll get at least acceptable results.
When I started with programming quite some time ago, I couldn't even draw stick figures (... sadly, no joke...) But then, I spent some class hours at high school with drawing instead of sleeping, and I think I'm quite passable at painting stuff right now.
Also, waiting in the bus ? Grab a piece of paper, and doodle some of the ugly passengers sitting around. Sitting on the toilet ? Take a notebook with you (the non-electrical version here ), and do some quick sketchups until you're finished.
Don't expect art to be somewhat easy and relaxing. It takes almost as much time as doing a proper design before coding, and requires the same attention to detail. Don't expect drawing to work on an instant, sometimes you need to do entire parts of an image again.
If you intend to do proper graphics on your computer (i.e. non-pixel art), I also heavily suggest you invest in a graphics tablet. These come in handy sooner or later, and aren't all to expensive.
If doing 3D stuff you might try some texture generator, these give you nice results. For example, Genetica looks quite good (see http://www.spiralgraphics.biz/genetica.htm). You can also achieve similiar effects in Photoshop by heavy use of layers and various basic noise generators.
Another general hint: Don't work in the target resolution. You want a 512x512 texture ? Start with a two to four times as big one, draw there, and shrink down later. This usually has better results, since the downsampling "corrects" pixel errors.
Modelling usually isn't that much of a problem once you know how to draw. First, draw some sketches, then, scan them in and set them as a background in your modelling application. Model after the outlines of your drawing.
The style you should use depends on the setting you want to use it in. There is a difference between art done for a gritty urban setting such as in Max Payne, and the art used for another installment of the Sonic series.
First, think of a general setting. Then, determine the basic style. Now, you can think of more elaborate styles for each different scene/level of your game. Style is created by repeating elements all over, so keep that in mind, and do that repetition by design, not on random. Also, when playing other games, spend some thoughts on how their style is defined and remains consistent.
Hope this helps,