its not that hard really....all you will have to do is

(SPOILER)First go on a Regular walk..you will get a different cut scene then usual. On this on choose lookover your chocobo not look for treasure. Next take a short walk and again a different cut scene will happen. Then it will say your chocobo looks busy or something and you look for treasure then and you will find the hankerchief you gave it a while back.

After that talk to the guy again and you have your very own lvl 20 all job chococbo whistle.

Enjoy!