Grind. A lot of grinding. Personally I havent seen a single person with a Lv10 Chocobo nor heard of anyone getting it.

Its a bit of a time waster but best way to Level up your chocobo is fighting Lv50 Enemies, (such as the water sprites in Urth's Gift near Quarrymill in Gridarnia)

Since your Chocobo gets exp based on part on the EXP you get from a mob, bonus EXP bonuses helps AND since you can gain Chain EXP fightning Lv50 enemies as a Lv50 Class/Job, it makes it easier.

You can also alleviate your grindom by buying numerious items to equip and spiritbond them, and get materias after your done.

You level up your companion AND you get a profit out of it.