Hmm, well if you have 0 stars and win a battle you get 1 star. Win 2 more and get a second star. Win three more (or win 2, lose 1, win 2) and get a third star. etc.

That's what I have observed in my experience.