You can start doing this right after you get the Highwind, although you might want to wait until Cloud rejoins you, because then the Gold Saucer will reopen. First things first, go buy some stalls for your chocobos at the Ranch. Now you can head out and find some chocobos for your first endeavor.
The River and Mountain Chocobos (turquoise and green respectively) can be acquired by mating a Good chocobo with a Very Good chocobo. The Good chocobos can be found in the Gold Saucer Area, where they hang with two Spencer enemies or two Flap Beats (the chocobo must be in front of the Flap Beats, or it'll be a dud). The Very Good chocobos are in the Rocket Port area, where they hang with two Kyuvilduns or two Valrons. If you find chocobos that aren't with these enemies, they'll be no good. Once you have one of each, a male and a female, you'll want to get them into shape and get the proper nut, the Carob Nut. This can be stolen or won from Brachioladus, the red dinosaur-like creature roaming the green parts of Icicle Area. You might want to get two while you're there, since you'll need two anyway.
Now, although I've heard it's possible to get the kind of chocobo you want without racing them, the odds of doing it must be next to nothing because I've never done it. At least get them up to Class B before attempting to breed them for a River or Mountain chocobo. When you're ready to breed them, save, then go in and mate them, giving them the Carob Nut you just got. With a little luck, you should wind up with a turquoise or green chocobo. Take note of its color and gender. Now you can wait until the parents are ready to mate again, or you can scrap them and go out and get new parents (this is a little faster and probably easier on the gene pool, too :-). Whatever the case may be, try again to get the other color and gender, and make sure to use another Carob Nut!
Now, you'll probably have to go do the next scene or something to give the new chocobos time to mature a little. In the meantime, you can take them out for a spin, as the whole idea of raising these things is to get treasure. That's right, if you ride your River chocobo out by the islands east of Mideel, you should eventually find a cave that holds the Quadra Magic materia! If you take your Mountain chocobo out into the mountains south of Wutai, you'll run into a cave containing the Mimic materia! Wow, pretty good prizes, huh? And there's more to come.
Get your green and turquoise chocobos in shape (at least to class B) at the races, then mate them. It doesn't matter which nut you give them. The odds are fairly high that you'll wind up with a lovely black chocobo, which can cross rivers and mountains. If you take him into the dirt around the North Corel Area, you'll stumble upon a cave leading to the MP/HP Switch materia, which, admittedly, is extremely lame. But, well, anyways, when you get the chance, load that black chocobo up with Sylkis Greens, because you'll need to race him all the way up to Class S. If you use the cheat (hold R1+R2 during the race) you shouldn't have a problem.
To get the fabled Gold Chocobo, you'll have to first get a Zeio Nut from the goblins on Goblin Island. Then you'll have to get one of the Best chocobos from the northwest corner of the Icicle Area. You'll know them because they ONLY hang with the bunny-rabbit enemies (They're called Jumpers). Get one of the opposite gender of your black chocobo, feed him some Sylkis Greens, and race him until he gets to Class S. When you're finally ready to mate the best chocobo with the black one, give them the Zeio Nut and cross your fingers. If they're both Class S, the chances are pretty high that you'll get the Gold Chocobo. Now you can ride him over the sea into the northeastern corner of the map, where the Knights of the Round await on Round Island! Oh happy day, the Knights of the Round! I don't know, but to me, all that chocobo raising is worth it for this summon spell.
And that, my friends, is how you breed chocobos. Exciting, isn't it?