It is actually not too difficult.
When you are modifying anything via 3dsmax then you have to do this:
Download UVMapper Classic from here:
http://www.uvmapper.com/download/uvmapper030a.zip and run this. You have to use this to open your modified model mesh and this basicly "unwraps" the model mesh and allows you to save a unwrapped wireframe copy of the model and this is what you use as a template to create your textures with. Creating textures from scratch however is not exactly easy if you have little experience with Photoshop or Gimp...etc and it will require at least some knowledge on how to use one of those apps.
My personal technique however differs from this and is actually extremely difficult but allows me to have a lot more precision when I create textures...not to mention the technique I use requires a lot of experience in both 3d modeling AND photoshop (I do not use gimp or paintshop pro).
What I suggest however if you have little experience with doing this in general is to at least look up some basic 3d modeling tutorials on the internet, practice with the basics and get familierized with the chosen 3d modeling software and graphics editing software by creating primitives (sphere, torus, cube, etc) and practice putting textures on those using uvmapper classic to make the template on each one and gradually move up from there.
While I myself have some extensive knowledge about 3d modeling and photoshop, I however do not atm have the time to do one on one tutoring and I am currently super busy with the mega-mod to have time to write a proper tutorial for doing this.
Hopefully this helps a little bit and everything I said above I suggest to everyone that wishes to do model modding rather then just a simpler texture mod.
little piece of advice for you: 3d modeling IS hard and is not something that just anyone can learn to do. I myself have been doing 3d modeling since around 1995 (that is technically when I first learned it on my own via trial and error) and I have been using photoshop even longer (since 1991) so I have learned probably in the hardest possible way anyone can learn since I never looked at a single tutorial and just figured everything out on my own and even invented several techniques along the way which have in effect saved me some time when working on any models that are complicated.
If you want I can link you to some tutorial sites that give excellent tutorials for really getting this down...several even are about modding game models too so those can be used for what you want to do.
Also...remember, when you edit any game model the texture it was using becomes invalid since adding or removing vertices, polys, etc will change the surface area of the model mesh and thus cause the texture to not work proper since it was made for a different surface since the texture is just the mesh of the model in a unwrapped state.
Think of this as wrapping up a cube with paper....take the paper off carefully without tearing it and use that same paper to either wrap a sphere or a rectangular box....if you do that you will notice the paper will not properly fit. This is the best analogy I can use to explain why the textures screw up if you modify the model in any way without making a brand new texture.
Any questions about what I have said here...just ask either in this thread or pm me...I or someone else will try to answer them.
If you already know all or most of this then I apologise but I am just assuming from the way your post is written that you may be new to doing this.
