It isn't just the nonce that increments to find a valid hash, you constantly hash the block header completely. The block header contains other data such as version, hash of previous block header, merkle root, time and bits. Your merkle root hash will be different to everyone else. This means no-one else is hashing the same data.
More newbie questions... Does everyone have the same transactions? Why do we have different merkle roots if we have the same transactions?
As a miner how do I get transactions? How often will I get more transactions? Do I have to recompute the merkle root each time I get a new transaction and then restart the nonce? This sounds like a job for Sisyphus.