Palomino Creek, Red County - Inside the graveyard in the southwest corner of Palomino Creek.
Whetstone - By a pile of coal on the east side of the Angel Pine Junkyard. From the Angel Pine Safehouse, go south and turn right at the next intersection. Go through the next two intersections and turn right at the three-way intersection near Mount Chiliad. Follow the road until you see an area with huge machinery on the left side of the road. This is the Angel Pine Junkyard. Enter the Junkyard but go close to the south wall as you proceed east through the facility. After climbing over some large blockie stuff you should see a very large container crate and a pile of coal to your left. Turn left at the corner at the end of the container crate and you should see the Shovel.
Ocean Flats, San Fierro - In front of a beige and white house facing the beach. From the entrance of the Ocean Flats Ammu-Nation, head west through the intersection and to the three-way intersection where Wheel Arch Angels is located. Turn south and then turn west at the next intersection. Continue west until you reach the three-way intersection with signal lights. Head south. Look to your left. The third house down should be the beige and white house. The Shovel is in front of this house.
Hunter Quarry, Bone County - Near one of the half-buried crates just west of the rock crushing machines at the bottom of Hunter Quarry.
Prickle Pine, Las Venturas - In the northeastern part of the tennis courts for the apartment complex in northeast Prickle Pine. From the road entrance of the Yellow Bell Golf Course, go north and follow the curve east. Go east along the road and you will see a curve going south. You will also notice a chainlink fence and an apartment complex beyond it at the curve. Go straight and smash through the fence. Continue east past the swimming pool and to the the tennis courts for this apartment complex. The Shovel is in the northeast corner of the northeast court.