Collect the chocographs and find their treasures. You'll get one that brings you to the fat chocobo. He'll upgrade your chocobo. Every chocobo will have that ability. Later encounters with the fat chocobo (through the same means with different chocographs) will result in better chocobos until you get the gold chocobo.