The Shovel is a piece of equipment that can be found in a temple on Tenerife island, near the saloon. Once obtained, it can be used to dig through blocks and to dig up buried treasure by pressing Down+A on land.
Getting the Shovel will require you to enter the temple on Tenerife island during certain times of day when the doors are open. Once inside the temple, there are some enemies which are difficult to get past if you are not wearing the Top Hat. Below that is the chest containing the Shovel.