Named after the tendency of domestic cats to bury their excreta, a cat hole is a small hole1) dug to contain solid waste. It is dug away from from the immediate campsite and water sources, and is covered after a single use.
A multi-use variant is a slit-trench latrine, which is basically a series of cat hole dug at once in a straight line (a narrow trench). It is straddled and used at one end then that portion covered – in this manner the trench gradually fills up from one end. Downsides are concentration of excreta in one area. Upsides include reduced overall digging effort, and the ability to use the latrine without digging an individual cat hole in real time.
Leaving toilet paper in the cat hole is a matter of local policy:
Check with the local BLM/NF website or collateral materials for guidance on proper cat-holing procedure in the area.
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.
Note: secessus has begun using/recomending a mattock for cat hole digging duties. His was $10 at at flea market. Others have reported success with this portable version.