This quest takes 6 real world hours to complete (or 6 Vana'deil days). These do not have to be consecutive hours, i.e. you can break them up by doing other things. You also must be greater than level 20.
First, you will need 4 Gaussebit Grasses. You could get them all before hand, get them all during, or whatever you want. Note that they do take up 4 spaces in your inventory so if you wanted to get half before and half during feel free.
To start the Quest, talk to Brutus in Jeuno Upper near the Chocobo Stables. He will be a dink and say you're scum and not worthy to ride chocobos. Next, if you have the grasses, talk to the little boy next to a sick chocobo and try and feed the grass to the chocobo. The chocobo will not eat the grass.
Come back in an hour and try to feed the chocobo again. Again, you will be rejected. Come back and hour later and repeat, this time the chocobo will eat. Rinse and repeat 3 more times (you'll have some cinemas in there) and after 6 hours of this you'll have your license.
One thing to keep in mind is that you can buy these grasses from the AH. Some people feel their time is worth more than the money it costs to buy the grasses and will just buy them from there. I'll admit I bought half of my grasses from the AH. Of course, keep this in mind because obtaining the grasses at this level is relatively easy, and if you stock up on them and sell them at the AH you can turn a tidy profit.