I just base it on teh hd. If the guy can have a cohort of 5th level let's say, that's a 3HD animal + 2 HD from being awakenened. Once you can have a cohort of 6, that animal can start taking class levels.
We've used it in a couple of games, and it seems to work out well.