Once you leave Lindblum through Dragon's Gate on your way to Gizamaluke's Grotto, you can make a pit stop to the Chocobo Forest heading east across the Mist Continent.  There you'll meet Mene, a moogle who's looking for Choco.  Use the Gysahl Greens you get from him on the tracks just outside the forest to get Choco.  You'll then be able to play the Chocobo Hot and Cold game where you get 60 seconds to try and find some buried treasures on the playing field.  Occasionally you may find a Chocograph, an item that gives you hints on where some treasures are buried on the world map.  Some of these Chocographs will also allow you to upgrade the status of Choco as well.  He'll start out yellow, which doesn't have any special abilities, but you can get light blue (shallow water), red (mountain), dark blue (sea), and gold (sky) chocobos.  Each progressive color also maintains the abilities of the previous colors as well.  Also at some point, Mene will tell you that you can't find any more Chocographs in the Forest and that you'll have to go to the Chocobo Lagoon.  You can find more Chocographs there, but later on Mene will tell you again that there aren't any more Chocographs there.  You'll have to return to the forest, and then back to the lagoon again, and by then you should get the Gold Chocobo so that you can go to the Chocobo Air Garden to finish finding Chocographs.  You will also find a few Chocograph Pieces.  There are six of these and when you find all six they'll join into the Chocograph that leads to the Gold Chocobo.  Note also that you cannot complete this entire side quest until you get an airship on Disk 3.  Listed below are the chocographs and what you can find within each treasure chest.  They are in the order they appear on the menu, not the order that you will find them.  Partway through your search for items you will also find some Dead Peppers which increase Choco's digging power.  These allow you to reach Chocobo's Air Garden after you get the Gold Chocobo, Chocobo's Paradise, and also find some more hidden treasures.  There's more info on the additional treasures and Chocobo's Paradise below the Chocographs.

Once you obtain the sky ability for Choco, you will be able to reach the Chocobo's Paradise.  Fly with Choco to any corner of the world map and you will find a hidden island.  Land and look for a crack in the mountain.  Now use a Dead Pepper on that crack to open up Chocobo's Paradise.  Here you will find Fat Chocobo who will tell you there are more treasures to be found in the world.  Once you find all of the treasures you can return to him to get the Fat Chocobo Card.  Here are the rest of the treasures you need to find in order to get that card (you need to use a Dead Pepper in these locations).  For the ones in water you will be looking for bubbles in the water and on the land there's a crack in the mountainside.