In one of your level 20 main scenario quests you'll be prompted to join a Grand Company. After doing so pretty much anything you do will get you a small amount of company seals (dungeons, FATEs, guildleves, etc), which can be exchanged to your GC's headquarters for various goodies. You need 2000 of them to get the Chocobo permit, which will trigger a small 2 or 3 step quest to get your own personal chocobo. It doesn't take long to get 2,000 seals, maybe 30-45 minutes.