Steps to get a mount:

1. Reach level 20
2. Progress your main story. After the level 20 trial "The Bowl of Embers", your next story quests will involve you choosing your Grand Company allegiance.
3. Select one and officially join it, and a quest will appear at your GC's HQ (I believe it's entitled "My First Chocobo"). You'll need to accept that quest.
4. To purchase the Chocobo Issuance for the quest, you'll need to gather 2000 Grand Company Seals. These can be obtained through GC Leves (try Moraby Drydocks for the first GC levemete), through fulfilling the Grand Company section of your hunting log (Try going to the optional dungeon Halatali for a bunch), or through completing FATEs (higher level FATEs give more seals). Turn the seals in at your HQ for the Issuance, then complete the quest.
5. After naming your chocobo and completing the quest, your ability to ride all mounts will be unlocked (including your new chocobo, but also any Collector's Edition bonuses, etc).