Named after the tendency of cats to bury their excreta, a cat hole is a small hole1) dug to contain solid waste. It is dug away from use areas and water sources, and is covered after a single use.
Leaving toilet paper in the cat hole is a matter of local policy. When paper can be buried, it is left in the bottom of the hole. When paper cannot be buried, it is packed out in zip-loc bags or similar.
The use of a narrow "trench spade" shovel will be easier than a broadheaded shovel in hard earth conditions. Plastic camping trowels are light weight, smaller in size than a spade and work well in soft soils. Metal garden trowels, while heavier, will stand up better to rocky or hard soils.