The quickest and cheapest way to get there from Brutus is to simply run southeast out of the tunnel.
The (J-10) Chocobo Spoor is located between the AT-03 Martello and the Ignis Erucas. You can reach it by Conflux #07 or #03.
Trade the Gysahl Greens to the Chocobo Spoor and it will tell you, "You'd best observe from a distance..."
Run a short ways from the Chocobo Spoor and a Chocobo will spawn close by.
It will run around, stop, spin a couple times, and then run to another location.
Approach when it has its back to you and click on it from behind to get the message, "You've caught yourself a chocobo!"
The Chocobo seems to have a very narrow line of sight, approaching from the side works fine.
The Chocobo has a distinct pattern, usually a dash, then a long look away, then a small trot, quickly followed by a turn (don't try during this phase as it always turns as you come up to it then back to the dash, repeated.) It also only walks/runs to 4 locations around the Spoor and will only face particular directions at each spot, using this information it's pattern is easily observed, once you get it, it becomes laughingly easy to catch.
If you approach when it is facing you, it will say, "Kweh!?", be spooked, and run off to a new location. The Chocobo may randomly run deep into the Coeurls or chasm tunnels and disappear.
There are two "levels" of spooking the chocobo. If you click it while its looking at you, it will say "Kweeeh Kweeeh!" and run away, to my experience into the Coeurls.
The "Kweeeh Kweeh" message is received if you click the chocobo after it is already spooked. if you get the Kweh Kweh message twice before it de-spawns it will stop and go back to the normal area. you can have another chance to finish the quest if it does not see you on the way back.
If this happens, you must obtain a new bunch of Gysahl Greens on your own to try again. Changing area does not reset it.
Having some Gysahl Greens in store makes unnecessary running around unneeded.
Return to Brutus to complete the quest and receive your reward(s).
Only one person can do this quest at a time. If someone else is doing it, you must wait for them to catch the chocobo before trading your Gysahl Greens. You cannot trade the Gysahl Greens until 60 seconds have passed since the chocobo was last caught.
It's possible for a full party with the quest active to all receive credit for the chocobo catch, no matter who pops or catches it. It's even possible to receive credit while still standing next to Brutus when the chocobo is caught.
The minimum target radius seems to be rather small. Can often get "Target is too far away." message, so be sure to get up on it.