Where to start.

Just look up tutorials or buy a book on whatever you want to learn. They are all essentially the same. Watch timelapses on youtube and look for step by step tutorials.

Start with modelling,unwrapping and texturing of none organic models. No sculpting,rigging,baking or characters at first. A simple standard crate/box , unwrapped and textures would be a simple task to get a feeling for the use of the tools. You will gain not only skills in using a certain tool, but in doing game art.

For texture works you should use a painting tool like gimp (very similar to photoshop, but free).

Art is like music, you need to learn one or more instruments (modelling,texturing,rigging, scupting tools) where the brand doesn't really matter at first (brand=blender,3dmax,maya). But to be a good musicain you need to practice,practice, and practice... , the same occurrs to being an artist.

I want to say that pretty much any model looks good with a great texture. So texturing and thus knowing photoshop (or something like that, gimp is free) is a great advantage. Like Asha mentioned put down a box, unwrap it and texture it, but texture it multiple times with a different look and feel. Then you might want to do a barrel, then a treasure chest and apply some extra maps to it like a normal and specular map. Now you know what it takes to unwrap models and texture them, this will be a advantage since you know what to model and what to "paint" on your model. There are many props you can model this way and get used to the program, speed up your workflow and finish things.

Like programming, keep projects simple. When you finally feel up to it try a car tutorial, there are plenty of them and most separate all the individual parts.

Organic modeling takes a lot more, loads of refs, good eye for proportions and anatomy. Even for alien monsters you need to make it convincing looking. Drawing skills really help here since you already know the shape of, let's say, a head by shading/rendering by pencil. I suck at organic modeling and i feel my bad drawing skills influence that. Since i slowly started learning drawing my organic models are better so drawing might be something you want to learn too.

Finally when you got some models done, get mudbox or Zbrush, also complex programs but they allow you to detail your models by drawing on them. You can also sculpt models from scratch with it but high poly and when you know regular modeling you could build a low poly cage around that model and bake the high poly into the low poly for sick detail. But this should be your last step since knowing how to model and texture is essential for real time models.

There are plenty of sites you can ask for help, i really like: GameArtissans and Game artist. 3Dpalace is also a very helpful community with there own video tutorials and 3Dbuzz also offers a lot of free video training. Although most of the tutorials are for programs like 3D max if you know your way around in your app you can still learn a great deal from them like edge loops and poly topology.

GL!