My understanding of the mining mechanism is this:
- The miner connects to a Bitcoin client (or pool) and submits a getwork request
- The client (or pool) responds with a chunk of data containing the block data, including the randomized bits, and the nonce (the bit which the miner changes)
- The miner increments the nonce multiple times until it either finds a solution or overflows, at which point it submits a new getwork request to the client (or pool)
Since the client/pool is responsible for handing out the getwork requests, the client/pool is also responsible for guarding against duplication. Since the entropy of the data handed out by getwork must, by definition, be greater than or equal to the output entropy of SHA256 (2^256 bits) it should have the same or lower chance of collision (1/2^256).
In this case a "collision" would be handing the same work to multiple miners and so we can say that multiple miners being given duplicate work has so low a risk of occurrence as to be a negligible risk.
One of my favorite comp sci professors once told me that the chance of such a collision (per unit of work) is about the same as winning the state lottery 11 times in a row, then being struck by lightning, surviving and being elected president. And he had the math to back this up...