Once you hit level 20, you need to get to Jeuno. It's a long trip without a Chocobo and can get dangerous, so you'll want to get some high level help or take lots of sneak/invis items to make it safely.
In Jeuno, head to the Upper Jeuno Chocobo Stable and talk to Brutus a few times until he says "What's your problem? You wanna ride a Chocobo?" and asks you 2 questions. Once you've answered those questions, obtain 4 Gausebit Grass (Auction House is the easiest way) and trade one to the Chocobo standing in the corner next to Osker. You'll get a short cutscene and it won't eat.
Wait until the next in-game day (0:00 on the clock or later) and trade a Gausebit Grass to the chocobo again. Again, you'll get a short cutscene and the chocobo won't eat.
Repeat this 4 more times, it will now take one Gausebit Grass per trade. When you trade it the last one, it completes the quest and you get a key item "Chocobo Permit".
Now that you've got your chocobo permit, you can rent chocobos in all cities except Mhaura, Selbina, and Nashmau (These towns are considered too small to have stables) There are also "Chocogals" in a few places around the world, all quite close to the destination point for Teleport spells. You can rent a chocobo in the 3 starter cities at level 15, or anwhere else at level 20. The rental lasts for 15 minutes if you're below level 20, or 30 minutes at level 20 or above. When the timer runs out or you dismount, the chocobo runs off and you're back on foot.
Chocobos won't go into any city or dungeon zones, but you don't have any other restrictions about where you can go. You do not get any aggro on a chocobo, so be careful when you dismount or you might end up in a messy situation.
It's also possible to get your own pet chocobo that you can call without having to go to a stable, but that's a hugely complicated process. You can go to
http://wiki.ffxiclopedia.org/wiki/Chocobo_Raising for info on that, but it's not something I'd advise doing when you're first starting out. It requires a lot of time and money.