Chocobo Breeding is a time consuming and expensive procedure that can yield fantastic results. This is my take on Chocobo Breeding, taken from several other accounts and laced with my own attempts.
The Green/Blue Chocobos
Green and blue chocobos are bred mating a "great" chocobo and a "good" chocobo with a Carob nut. These nuts are impossible to be bought (except at the gold saucer, I think) and are found on the vicious monsters called the Vlakadorados. These monsters have over 30,000 life, their attacks are fairly weak. The large amount of life gives you ample time to steala Carob nut (they morph into elixers). I found great success in mating a "Great" Chocobo male and a "Good" chocobo female. Most guides will say racing your chocs up into the "S" class gives you a better chances, but I recieved a blue/green chocobo EVERY time I mated these two, and they were only in the "C" class (although it took me a while to actually FIND them... more on that later). Green Chocobos can cross most mountains, and Blue chocobos can cross light blue oceans, like the Tiny Bronco. Using these abilities gives you the Mime materia and Quadra Magic materia.
The Black Chocobo
Black chocobos are bred once again with a carob nut, but the parents must be a Green and Blue chocobo. I got this one first try using an "S" class female blue chocobo, and a "C" class male green chocobo. The Black chocobo can do everything a Blue or Green can, as well as a little more. They can cross the cliffs that Greens can't and they can cross the rivers that the Blues cant. This opens up a whole nother materia cave, allowing you to get the HP<->MP materia.
The Ultimate Gold Chocobo
These Chocobos are capable of taking you anywhere. They can cross oceans, any mountain or cliff, and every river. These are also the hardest of all to breed. You will need a Zeio nut, which is found on an island to the northeast. Goblins carry them, so you can take them either by killing them and hoping to recieve one after the battle, or you can steal from them. Once you have a Zeio nut, use it to breed a Black chocobo and a "Wonderful" chocobo. I cannot remember which one of these was male or which was female, but I do know that I got the Great Gold Chocobo on the first try while they were both "C" class chocobos. Using the Gold chocobo, you can proceed to the Materia cave in the middle of the ocean... and within it, you will find the mother of all summons: the Knights of the Round. This materia can deal upwards of 70,000 damage to all targets, and can kill Bizarro Sephiroth in one hit. After that, I use it instead of the Highwind to get around, since it can go anywhere and cross anything... that way, I dont have to park a long ways away, and trek to the town or whatever (an example of this is Cosmo Canyon). Have fun!