Dude, before we get started, I have been using Maya for 2 years, and would advise you do all you texturing in Maya. The UV editor is far more powerful than lithunwrap or Milkshape.
Just go to view--> UV Texture WIndow.
You can add planar, cylinder and pelt map to your meshes, as well as editing the way the mapoer works, in the atributes on the right. You can get a direct X exporter for maya, that supports both static and animated meshs from the Direct X SDK (google it).
All I'm saying is that Maya is like £980 more than Milkshape, and is far more powerful. Id stick with it, read some tuts and get your UV mapping down in it.
With regards to high poly... forget it man. The only benefit of going super high poly is being able to create tasty Normal maps for your low poly model.
Quote: "if their models are such low poly, why do they look so great? "
well, that would be down to the quality of the texture and the use of shader maps. THe whole point of a normal map, is that you can save on poly-generated detail by generating it in the texture