How do you get a chocobo?

You have to do the story quest until it make you apply to one of the three Grand Companies (I think it's around lvl 15 or 20). Story quests are marked with meteor shaped icon.

After you apply to one of them, simply talk to the NPC in the grand company that let you exchange items for seals, click the Material tab, and Purchase the Chocobo License (of course you will need some seals for that).

After that show your license to the chocobo breeder NPC, and he will give you your very own chocobo and let you name it!

Good luck~