oke doke,
First thing is smooth your model so you get predictable results from textures and the rig. I would advise not using the smooth proxy preview as a final mesh/ to define large changes in shape, you can get some odd results. Use it to help you model more easily or to get smoother edges at render time.
When I rig, I set max influences to 1 as my initial bind, go into my paint weighting tool and make sure everything looks as it should (no joints controlling mesh it shouldn't) I then lock the weights on all the joints and increase the max influences up to 3-4 and then slowly unlock two - three at a time and smooth the results.
This is a quick explanation, if you need something more in depth just shout.
FX supervisor - double negative