The answer is that the puzzle is huge and non-determininstic. The puzzle is to take a block of data - all of the transactions that haven't been confirmed yet - and append a value to it that makes the hash of it below a given number. That number is called the difficulty, and is dynamically set. Systems trying to solve it simply keep trying different values and running the hash to see what the value is.
Any particular guess-and-hash operation has a certain probability of finding a solution, and that probability is the same for all systems, no matter how fast or slow they are running. Faster systems just guess-and-hash faster, and thus have more opportunities to succeed. That difficulty is set dynamically based on the estimated total rate of operations, or hashrate, of the entire network, so you can think of the system overall doing a certain number of hashes per second. A solution is essentially a random event that one particular hash will satisfy. So the higher the hashrate, the higher the probability that you will succeed, but it's still a probability. You never have a guarantee that you will succeed, no matter how fast you are, and even slower systems have a chance.
That's why there are these malware-created networks of low-power systems doing bitcoin mining. They're all pretty slow, but with enough of them working, one of them will succeed every once in a while.
I think you have to add that everyone is solving a different puzzle, I.e. if I'm not mistaken, an identifier of the miner (I would guess her public key, I can't really check right now) is included in the string she hashes (plus they may not all have the same list of pending transactions). otherwise you would still have the problem that if people use the same software for guessing the random string, the fastest would always win.
True, but not really relevant to this. Even if they were all the same, it wouldn't change things. The fastest would indeed win if all hashing devices started at the same nonce value and all incremented it in the same way. (the nonce is the extra data put into the block solely to make the block's hash meet the requirements) But precisely because of that, there is no reason for any device to try nonces in a deterministic way.
maaku's explanation makes clear a very good point - trying any particular hash only tells you whether that one succeeds or fails; it doesn't tell you anything about whether any other value will succeed or fail. Any particular hashing device will maximize its chances of winning/finding a solution by trying nonces in such a way that it is unlikely that any other device is trying the same ones, but that it never tries the same one itself twice.
I don't know offhand how many mining algorithms are out there and how they go about picking nonces, but I'd bet they do something like pick a strongly random starting value and then increment it by a fixed, small amount each try.
But yes, all of the miner's blocks are generally different. Each block that a miner is working on must have special Coinbase transaction that awards a specific number of new BTC to a chosen address. If you are an independent miner, that would be your address, but pool miners generally use a pool address. I don't actually know how the latest pool mining algorithms work, but I think they all have more elaborate systems for how payouts work.
The block being hashed will include the payout address set by the miner, which will make the block he is working on different than the ones the others are working on.
The block includes a nonce, a random number which is changed for each try until one gives a hash < target. That nonce is picked at random independently by the miners, so that also makes the blocks they are working on different.
Any particular guess-and-hash operation has a certain probability of finding a solution, and that probability is the same for all systems, no matter how fast or slow they are running. Faster systems just guess-and-hash faster, and thus have more opportunities to succeed. That difficulty is set dynamically based on the estimated total rate of operations, or hashrate, of the entire network, so you can think of the system overall doing a certain number of hashes per second. A solution is essentially a random event that one particular hash will satisfy. So the higher the hashrate, the higher the probability that you will succeed, but it's still a probability. You never have a guarantee that you will succeed, no matter how fast you are, and even slower systems have a chance.
That's why there are these malware-created networks of low-power systems doing bitcoin mining. They're all pretty slow, but with enough of them working, one of them will succeed every once in a while.