Chocobo Breeding can be very expensive if you want a high chance of success and it is going to be a damn sight quicker if you have the Highwind (and not the Tiny Bronco). First, to get a yellow chocobo, simply go to any set of chocobo tracks, with the Chocob Lure materia (availible at the Chocobo Ranch) equipped, and kill the monsters surround the chocobo when you get a fight. You may need to feed the chocobo some greens mid-battle if it is going to take you a while to kill the monsters. If you get the chocobo you'll be able to ride it around the map. If you've rented some stables at the ranch (10000 gil each), you can dismount and send it to the stables, where you can name it and find out its stats. If you haven't then it will run away if you dismount.
I advise you read the other useful tips at the bottom of the page before you start breeding.

To get coloured chocobos:

• Rent at least four stables (10000gil each) I'd recommend you get all of them.
• Capture Great Male, Great Female, Good Male and Good Female chocobos. Goods can be found in the tracks to the South East of the Gold Saucer. Greats can be found in the tracks west of Mideel (the place where you found Cloud after he got lost).
• Go to the plains just south of Bone Village, the excavation site at the south of the northern continent. Walk around the grass and you will eventually fight a Dragon type thing. It is very tough but foesn't hurt much and you'll never fight it if you have Enemy Lure Equipped. Try to steal from it. Eventually you should manage to remove one Carob nut every time you fight it. You'll need at least three of them. You can also get these by swapping 500GP for the first mysterious item in the Wonder Square of the Gold Saucer.
• Breeding your Great Male with your Good Female, using a Carob nut, should give you a blue (river chocobo), which should be female.
• Breeding you Great Female with your Good Male, using another Carob nut, should give you a green (mountain) chocobo, which should be male.
• N.B. your chances of getting green or blue will be greatly increased if the yellow parents are grade B or above. To attain this grade, win several races in a row at the chocobo. The easiest way to do this is to give each yellow 8 Sylkis greens (availible from the Chocobo sage in a clearing in the Northern Continent at a price of 5000gil each), these will make your chocobo win any b/c grade race easily.
• You should now have a green male and a blue female chocobo. Release the now-useless Yellows
• Get these up to grade A by winning several races in a row. You should only need about 6 Sylkis greens each to win easily.
• You will need to have progressed through about 2hrs of gameplay before you can mate these two. Waste the time by racing and getting the Materia mentioned above.
• When Chocobo Bily doesn't say you can't mate them (you'll have to keep asking him to find out), mate them using your third Carob nut.
• Now you ought to have a black female Chocobo.
• By mating your Black Chocobo with a Wonderful Male Chocobo, using a Zeio nut, you will get a Gold Chocobo. To do this, both chocobos must be grade A. You can get Zeio nuts by going to the island in the far north east which is covered in forest. In the Forest, you'll be able to fight a Goblin (it is Goblin Island), you can steal Zeio nuts from it. Wonderful Chocobos can be found (I seem to remember) at the tracks in the snow in the west of the North continent.* These Chocobos will only need about 3 Sylkis greens to get up to Grade A.
• Waite another 2hrs of gameplay for the black to grow up (get the above materia and race). When the black is old enough mate it with the Wonderful with a Zeio nut.
• You now have a Gold Chocobo!

Head to the North East of the map using your gold chocobo (you can fly it with the Highwind to Goblin islands but that can't land anywhere beyond). There you will find an unmapped island called Round Island (completely surrounded by mountains and filled with trees - no access to Highwind - and one cave). Go into the Cave where you can pick up Knights of the Round, the most powerful materia in the game - 13 knights attack with different elements, all doing about 5000-6000 points damage each!!! Quadra magic has no effect on Knights of the Round cos that would be too powerful.

Go forth and kick some Fantasy arse (ass to americans).
This guide was constructed with the help of the Chocobo sage of the Northern Continent, K. Megura's FF7 guide and some other guides, which I found pretty much useless cos they used different names to the actual game. Maybe they were referring to non-UK versions of the game. I used the terms I got from the UK PC version of the game, translating from the other guides' names.

• Once a useful chocobo has been born, release its parents to make some room (you can't have more than 8 chocobos
• Every time you train a chocobo to the required level, save your game before going back in to the stables to mate them. If you don't get the Chocobo you want (there is always a possibility of this) you can simply reload your game instead of waiting until the two are ready to mate again.
• Sylkis Greens are very expensive. If you do not have enough money, go for a quick trip around the northern crater. Here you find lots of monsters all giving large quantities of Gil (as well as loads of experience and AP).
• Occcasionally when racing B-Rank chocobos, you'll be put against a black chocobo called TEIOH. You can try to beat it by preventing it from getting past you. Another tactic is to get it stuck behind the crowd at the start and make a quick get-away. You'll probably be put against it a few times in a row so keep trying until you get to a race you can win.
• When you've caught four Chocobos, save the game before going in to the stables. Apparently the gender of chocobos is not decided before then, so if you don't get the one you want, you can reload and you might get different ones