Actually, they iterate consecutively through the noncespace.
But hey, finding a needle in a haystack is in your favour searching consecutively if the needle is near the front of the haystack. Searching randomly, it doesn't matter where the needle is, it's random chance.
So then, how does each miner know what it should check? Surely there'd be a useless overlap. And "noncespace" is a cool word, mind if I borrow it?