After talking to Hantileon in Southern San d'Oria (I-11), inside the chocobo stables (upstairs), he will state that you have to return and check your bond with your chocobo, as sometimes they hide things. This does not mean that you have to have a high affection level. I found the Handkerchief with an affection level of 2.
Now, when you Go on a Walk, you get the option to search for an item or to watch over your chocobo. When it says "Your Chocobo is completely absorbed in its current activities", choose the search option. You now have a chance of obtaining a Handkerchief.
Occasionally the Chocobo will detect your search and it will fail.
A successful search does not necessarily result in finding the item. In that case, the item is not located in this area, and you should continue to look in the other 2 areas. The location does not randomly reset each day.
If your bond with your chocobo is exceptionally strong, you will receive a Dirty Handkerchief, which is also used for obtaining the Chocobo Whistle. When giving the Dirty Handkerchief to Hantileon in Southern San d'Oria, he will say: "You gave this to Chocobo when it was still a chick, didn't you? It looks like Chocobo held this item very dear. Your bond with your chocobo seems very strong. I have no qualms about entrusting you with this now."
Note that you cannot call your chocobo with the Chocobo Whistle until you register it with the VCS trainer where you traded your egg.
Once you have completed this quest and have your whistle, you may retire your current chocobo, raise a new one and register to call it without redoing this quest. Your whistle will call your new chocobo after you pay 250 gil.
You still get to keep the whistle even after obtaining the mount command.
If you drop your whistle, it is possible to obtain a new one. Trade the VCS Card from the Chocobo you would like to use to the VCS Handler where you raised your Chocobo. You may then select "New Chocobo Whistle" from a menu. Please note, you WILL have to pay 20,000 gil for the new whistle.
If you wait too long while taking care of your chocobo to obtain a whistle and your chocobo becomes retired you will have to start all over and raise a new chocobo to obtain a whistle.