Originally Posted by Me
Assuming you have a fully grown Chocobo; Go to San d'Oria Chocobo stables and speak to the 'Chocobo NPC' and he'll tell you something about requiring a bond with your Chocobo or something of the like. Now, go back to the stable where your Chocobo is kept and take your Chocobo for a walk, your Chocobo should turn away, and you'll be given the option to search for something (sometimes your Chocobo will catch you and you will have to take him for another walk to be able to search again). If you find it take it back to San d'Oria stables as proof of the bond between you and your bird and the 'Chocobo NPC' will reward you with a Chocobo Whistle.
Use it sparingly as each charge costs 1,000G, although the first 25 are free.