This depends on how much you like to soft-reset and keep reloading save files in order to get the best possible results. You have to pass a certain stage in the game, but since you've begun to ask you probably already know where that is. Nevertheless...

Got airship? Go to the Chocobo Ranch, and talk to everyone until you're granted the opportunity to rent stables. I hope you've gathered 60,000 Gil because you're probably gonna want all six of them for the sake of ease.

You've got your Chocobo Lure Materia? Cool. Head for Mideel; you're bound to know where it is by now. Find the Chocobo tracks and keep killing off enemies until you run into a Chocobo standing with creatures that look like silver prawns/shrimps. They're called "Spiral"; do not even bother to capture the Chocobo if there is any other kind of enemy present, Spiral is what you want!

Send two of these Chocobos back to your stable, head back to the farm, and save. Go in, ask to put each one in the stable. Choco Billy should remark "This is a great Chocobo!" at which point you choose to put it in the stable. The gender is randomly decided at this point (not when you originally capture it!) so if they're both the same gender, perform a soft-reset with L1, L2, R1, R2, Select and Start. Get used to this, you may be doing it a lot.

Now that you have two "Great" Chocobos of opposite genders, you've got two options:
a) Feed them insane amounts of greens to max out their racing stats (if you've just got the airship you won't be able to race them yet, but you'll still be able to breed them... your gold will just have sucky stats). Then go to the Gold Saucer and keep racing until your rank ascends to such a point that you can no longer win (usually "A" rank with a "great" Chocobo, you'll be lucky to even reach that with a "good" Chocobo but who bothers with those anyway?)
b) Just go right ahead and breed them.

Keep in mind that b) has a lower success rate, but will still work eventually.

Whichever you choose, go to Bone Village (northern continent, southern tip; remember where you excavated the Lunar Harp?) and run around on the plains (not in the forest) nearby. You'll run into a lot of enemies named "Trickplay" but will also encounter a creature named "Vlakorados", which looks like a heavily deformed red deinonychus dinosaur thing. You'll need your Steal Materia equipped: steal a Carob Nut from the bastard and waste him. Repeat until you have three Carob Nuts; if you're lucky, the first or second you kill will also drop one, shortening the process.

Head back to the ranch. Save. Choose to breed your two "great" Chocobos. Give them the Carob Nut when prompted, and with any luck a blue or green Chocobo will be spawned. If not, soft-reset and try again.

Two more forks in the road:

A green Chocobo: take it for a ride, get in the airship, land near Wutai (far western continent) and ride around until you find a cave guarded by a honkin' big mountain with no beach and no grassy plains (hence needing to land the airship elsewhere). Go inside, claim your "Mime" Materia.

A blue Chocobo: ugh, pain in the ass. You can get Quadra Magic with this but it's much better to wait until you have a black one as it's easier. Nevertheless, it's somewhere slightly north-east of Mideel but involves a lot of navigating shallow water until you find a way into a cave. It's easier with a black Chocobo as you can almost run in a straight line, save it for then.

Now go outside the ranch. I think you either have to complete five or ten battles, though I can't remember which. After you've done this, you'll be allowed to breed them again, to allow enough time to pass for the baby chocobo to be old enough to breed and the parents to recover from whatever the hell they're supposed to recover from. Save.

If it is not a chocobo of the other colour and opposite gender, soft-reset and try again. And by the way, yes you're going to be inbreeding them. That's the joy of chocobo breeding! It sometimes helps if you mate the green/blue chocobo to the opposite gender yellow one, as this seems to increase the odds of the other colour coming out.

With your blue and green chocobos ready, you've once again got the option of just breeding them or racing. Do whichever; either way you'll need to fight five/ten battles again to pass them time. Choose to mate blue and green, give them your third Carob Nut. You should now have a black chocobo.

a) Near Corel, there's a river blocking the way to a desert with a cave. It contains the barely useful HP<->MP Materia, mainly put in the game for comic effect; I've only ever found two uses for it.

Now you've gotta catch another chocobo! This time, head to the Icicle Area, and head west. You'll find some more Chocobo tracks, so land on the grass nearby and go for it! This time, you want a Chocobo that's standing with rabbits, named "Jumping", and rabbits only. If any other monster accompanies them (ie wolf things named "Bandersnatch") then waste the Chocobo along with the enemies and try again; the odds are a bit low but the amount of battles it'll take just to capture the bugger will let enough time pass for your final breed, especially considering what you've gotta do next.

Go to the ranch, having caught your Chocobo whose bunny friends you murdered. Save. Choco Billy will declare that it's "...a wonderful Chocobo!" and you'll get to put it in the stable. If you captured the wrong one, he'll state that he "really can't recommend this one" and you'll look like a cretin. It needs to be the opposite gender to your black Chocobo so soft-reset if it's not.

Overfeed them? Race them? Do as you please. But you're not ready for breeding yet!

Fly northest of the Chocobo Ranch, and on the map you'll see a small island with some forests. Land, and open the menu. Does it say "Goblin Island"? Goody! Run around until you meet some Goblins, and steal a "Zeio Nut" from one.

Fly back, save. Breed your black Chocobo to your "wonderful" Chocobo. If a Gold one does not come out, swear at your TV and soft-reset, keep trying until you've got it.

Now take your gold Chocobo for a ride, and head as far northeast as you can on the map, taking care not to loop over the edge. There'll be an island surrounded by mountains and full of forest; there's no way you could land an airship there!

Go inside the cave and procure your Knights Of The Round Materia. Reportedly, in the early days of the PS3, this summon actually slowed the machine down! It could even kick the crap out of the PS3!

Now, if you fed and raced your Chocobos, and likewise have overfed your gold Chocobo, it will have godlike stats and you'll never lose a race. Have fun racking up the GP at the races, you'll need it for the Battle Arena in order to get W-Summon and Omnislash, as well as for Speed Square for Cid's Flayer.

Hope that helps!