After completing McCoy's minigame and beating all of the Victory Gang members, Petasi suggests you either help out more dogs or "go to Rune Village and check out Rune Caverns".
Tancredi, a black pug will appear outside the entrance to Rune Caverns and he needs your help.
He says he lost his hat in Rune Caverns and he needs to get it back because it was a present from his daughter, hence the name of the mission.
He will say that there are cobras in the caverns, so one of them might have made off with it. There is only one cobra in the caverns and it has the hat.
You can either wait until his back is turned (which can be tricky, since it is constantly rotating 90 degrees at a time) or wait until it has fallen asleep then slowly walk up to it, then bark or howl.
The cobra will drop the hat, so take it back to Tancred, where he will thank you and give you a woof.
You may have noticed the strange statue in the back of the caverns. Tancredi mentions it, and says that if you were to put a Sniff Master Medal inside, it would open up.
Petasi will say he hasn't heard of a Sniff Master Medal before, and that they should go and ask Tao about it. Upon doing this, Tao will say he has told them about this medal before and he will send them back to Rune Village to find the Second Book of the Sniff Master.