Where do I start

You usually dig up treasures.

You bought the shovel, didn't you?

There's a shovel in the shopkeeper's store.

But now how do you find it?

A map would be helpful.

Have you talked to the Citizen of Melee?

You bought the map from the Citizen of Melee, didn't you?