There is a shovel in the cemetery in town, north west of the North Gate waypoint portal, as well as another near the teleporter on the starting beach, before you get to the 2 drunk guards.

BTW grave digging in Cyseal can be dangerous...