First of all, you learn that Chocobo and Mene are trying to get to Chocobo's Paradise, but they cannot do it on their own. They need your help. Sound simple enough. It's not that easy. To master this sidequest, Choco must have the abilities to swim, climb mountains and fly. Think you're up to it?
Finding and Diging

You can dig at one of three locations: The Chocobo Forest, The Chocobo Lagoon, and the Chocobo Sky Garden. Talk to the Mogli and choose the top option... you can dig for a set amount of time, which is different depending on the place you're at. When the Chocobo's "Kueeee" Sound gets long, you are on the right track, and there is an object buried nearby. Make sure you're always running, rather than walking. That way you will save as much time as possible. You can find cheap objects like potions which are worth one point, but at other times you can get slightly better stuff like Ethers. You can also find important Chocobo items... such as Dead Peppers and Chocograph pieces. Once you gain enough points, your Chocobo will gain one level and dig faster; however, while digging in the Chocobo Lagoon, it will dig at half the normal rate of the Chocobo Forest. Digging up four items in one game at the Chocobo Forest will get you 10 bonus seconds, while digging up four items in one game at the Chocobo's Lagoon will get you bonus points... unless you have a dark blue or better Chocobo. Without a dark blue one, you will only get 30 seconds and half of the lagoon area to dig in. When you get a dark blue one, the whole area becomes avilable and you will get 60 seconds. You will also dig much faster, and get the 10 bonus seconds after four items. You will also get a big bonus for digging up eight items in 70 seconds.

Sounds
what does it mean?
Kweh
No treasure nearby
Kweh!?
Getting closer to the treasure
Kwehhh!?
Very close to the treasure
" K-KWEHHH!!!
You struck treasure, there are different depts, so keep digging, for each treasure you find Mene adds 10 seconds

Chocographs
If you find a Chocograph while playing the digging game, you will get 15 points, and five bonus points. After you leave and return to the World Map, you can select to equip a Chocograph, which will display a picture. You must find a similar location at some place in the world and dig in that location until you find a treasure. The cry will get a little longer, just like in the digging game when you are close. Some treasure will be items, while other treasure will be upgrades. You can have two unsolved Chocographs from each digging game location until Chocographs will stop appearing at that location. The order you get the Chocographs in is totally random. Click here for chocograph list

Finding Chocobo Upgrades
There are a few chests that will teleport you to the Chocobo Dream World, in which your Chocobo will be granted a color change and new powers. Chocograph number two will give your Chocobo the light blue Reef upgrade, which will let you walk and dig on shallow water. Treasure number 12 will give you the red Mountain upgrade, which will let you basically walk anywhere on any continent. Treasure number 14 will give you the dark blue Sea upgrade, which will let you walk over deep water. Treasure number 20 will give you the white/goldish Sky upgrade, which will let you fly (by using the Circle Button) over a forest area. While you are flying, you can press Triangle and use a Dead Pepper, which will cause you to shoot up into the sky. If you use this ability over one of the large shadows on the ground/sea, you will shoot up to the Chocobo Aerial Garden. There are a few different places where this shadow can appear, including: the northeast, by the area where the Earth Temple was (it was always shaking), behind Alexandria, and to the southwest of the world on an island.

Chocobo's Paradise
After finding all of the Chocographs and digging up their corresponding treasures, it's time to head to Chocobo's Paradise. You'll need a Dead Pepper, an item you can find while playing "Chocobo Hot and Cold."
Pilot your gold chocobo to the most northwestern part of the World Map, where you'll find a hidden island. There's a forest for Choco to land in and a small mountain nearby. Look for a large crack on the side of the mountain. Move Choco across the ground to the crack, and then open the menu (press the Triangle button) and use a Dead Pepper. Chocobo will dig open the entrance to Chocobo's Paradise.

Now ride Choco to the right, where he will use the fountain as a springboard to leap up to the high platform. This is where Fat Chocobo presides. At this stage, the Fat Chocobo will indicate that there are still treasures to find on the World Map. Also, you are now able to understand all of the chocobos when they speak. The chocobo seated to the left of Fat Chocobo will give you 99 Dead Peppers. All the rest of the chocobos, including the two near the entrance, provide clues as to the whereabouts of treasures hidden in the world that you can find by using Dead Peppers.

If you've found all of the treasures, Fat Chocobo dictates that Choco must stay in Chocobo's Paradise. He gives you the ultra-rare Fat Chocobo Card, as if it's any consolation. But don't worry, Choco won't abandon his friends. When you move back to the entrance, Choco rejoins you for more adventures!