You need to catch three chocobos - two Greats and a Wonderful.

The Greats appear near Rocket Town alongside Valdron x2 and Kyuvildun x2, and near Mideel alongside Spiral and Spiral x2.

Wonderfuls appear near the Icicle Inn alongside Jumping and Jumping x2.

The breeding process is so:

Great + Great + 4 or more total combined wins + Carob Nut = 50% Blue, 50% Green
Blue + Green + 9 or more total combined wins + Carob Nut = 100% Black
Black + Wonderful + 12 or more total combined wins + Zeio Nut = 100% Gold