As I understand it, caching is generally banned within the boundaries of wilderness areas, with very few exceptions. On National Forest land, I believe it is legal, provided you are not destroying or much disturbing things, like digging deep pits, chopping down trees or brush, and basically making a mess of the natural setting.

I don't know about BLM land, but I would suspect it would be similar to NF regs. On private land, obviously the correct approach would be to seek the owner's permission.