The entire block header enters as input in the hashing process.
Along with nonce and some other fixed fields there is a "Merkle root" field in the block header that each miner has different.
So each miner can search the nonce range from 0 to the last - in order; because of different Merkle root each miner will have different block header hash for the same nonce and other fixed fields.
NOTE: Why each miner has different Merkle root? That's because in the transactions miners include in the block (from which Merkle root is derived) there is one special transaction called "coinbase transaction" that each miner has unique. Therefore the Merkle root is also unique. "Coinbase transaction" is included by the miner himself along with regular transactions and is the transaction that gives mining reward to miner's own address.