Referencing an old thread - http://forum.square-enix.com/ffxiv/t...nd-You-A-Guide

After you kill Ifrit, you should be able to apply to a grand company at their hq in one of the cities. They will give you a quest to earn 2000 seals and then get a chocobo mount.
Once you are level 30 and have a chocobo, you can go to Camp Tranquil in South Shroud (Gridania) and get a quest there to use them as a battle companion.