How should I insulate garage walls?
Vapor barrier (if any) goes on the warm side of the wall. That's the inside for those of us in the frozen North (on average, for the greater part of the year.) In central Texas I'm guessing that might be the outside, on average.

Best solution to messy irregular stud bays might be damp-spray (aka glue-spray) cellulose (not a DIY product, but really good at dealing with irregularities and no vapor barrier is needed.)