Well yes, advancement would be the normal method, but as you said animals dont gain skillpoints and in the case of a Paladin mount... its not *real* advancement, aside from HD, BAB and Saves it does not recieve skill points, feats etc.
I thought of real training. Going out with the horse and training it to jump. Are there any rules on that maybe?