You can obtain a gold Chocobo as soon as your team gets control of the Highwind. All you need is the Chocobo Lure materia, and six stalls for breeding (both are found at Choco Billy's Ranch). I suggest waiting until you get the W-Item materia, otherwise you need to spend a couple million on Sylkis Greens (from the Chocobo Sage). W-Item basically gives you infinite items that you can use during a fight. However you need two of the same item for it to work. While in a fight, use one of the item you want to duplicate. Then press cancel, then ok, then cancel, then ok...etc. and you will see your inventory increasing.

You need to catch three Chocobos:
1) A great female or male Chocobo from the tracks near Mideel.
2) A good Chocobo opposite of your great Chocobo from the tracks south east of Gold Saucer.
3) Finally you need a wonderful Chocobo from the tracks on the North Continent.

You need to get three Carob Nuts and one Zeio Nut:
1) Carob Nut - Steal from a Vlakorados in the grassy area south of the Excavation Site.
2) Zeio Nut - Steal from a Goblin in the small forested island in the north east corner of the map.

You need to feed each Chocobo greens:
Sylkis greens (from the Chocobo Sage) are the best. I recommend feeding each Chocobo 50-100 greens. It increases their stamina, handling, and speed.

You must race each Chocobo up to at least A-Class:
Go to the Gold Saucer to race. While racing press and hold L1+L2+R1+R2 and your stamina will go down slower. It's pretty hard to race your great and good Chocobos up to class S. But your wonderful, green, blue, and black Chocobos should all be class S. If they are all class S your gold Chocobo will have better stats.

You must breed four times:
1) Breed your good and great Chocobos with a Carub Nut. You need to get a green Chocobo.
2) Breed them again when they're ready with a Carub Nut and get a blue with the opposite sex of your green Chocobo.
3) Now mate your green and blue Chocobos with a Carub Nut. You need to get a black Chocobo with the opposite sex as your wonderful Chocobo.
4) Finally, mate your black and wonderful Chocobos with a Zeio nut and you should have a gold Chocobo!