....we've often stopped at Teec Nos Pos trading post (to buy stuff) on highway 64 near US 160, and were planning an overnight there once, but decided to head up to Cortez as an afterthought...just ask the nice people at the post if you can stay overnight. Last time we were there was in 2007...
....and I agree with an earlier poster: don't just camp on Navajo land without asking at least the local council...you'll likely be asked to move at some ungodly hour.
....there are also boondocking spots around Bluff, and another trading post (a rough looking white-washed building made from cinder block) a few miles north of Bluff on the 191 (near Hovenweep Rd) where we used to buy supplies back in the early 2000s (we've seen overnighters park there)...but that was a long time ago, and it may have been abandoned by now...