I'm actually in the process of writing an article that addresses some of these issues, but that doesn't help you right now. I will say that one of my sections is titled "Three P’s: Pencil, Paper, Practice." The next section is titled "Three Additional P’s: Practice, Practice, Practice."
Practice is definitely the most important thing, but I will say that you're going to get way more out of it if you have read up on the following principles:
I see people far too often who are otherwise technically good fail at those basic things, and it's much easier to get started the right way than make the wrong way a habit. The http://www.androidarts.com/art_tut.htm link of BagelHere's looks like it has a pretty good overview of texture and lighting/shading.
I would also strongly recommend looking at basic art classes (although consult with teachers about what the classes will actually be about since course catalogs are super obfuscated) since that'll take care of the practice part (since if you don't, you fail the class) and give you a lot of tips and feedback as you go along and be a thousand times better than any online/DVD/book tutorial.