The "puzzle" metaphor may not be helpful. The goal is always the same: create a block whose header has a sufficiently small hash value, less than the current target.
So every miner can create a block any way she wants, as long as it meets the general requirements of the protocol (all transactions are validly signed, block reward is no larger than the current standard value, etc), and then start varying the nonce value in hopes of finding one which makes the hash sufficiently small. There is no single centralized authority or protocol that hands out blocks for people to work on.
In practice, this means that no two miners are ever working on exactly the same block. Two different solo miners will have different blocks, because each will have a coinbase transaction that pays the reward to his own address. Two different members of the same pool will be assigned different variants of the same block, in order to avoid duplication of work (perhaps each will put his own identifier somewhere in the block).
The target is, in some sense, uniquely determined by the protocol. The Bitcoin protocol specifies how the target is to be computed, based on the timestamps of prior blocks; this is what ensures that it adjusts with the total mining power of the network to keep the block time approximately constant at 10 minutes. It should be the case that all miners on the network are using the same target value to compare with their blocks.
So in that sense, everyone is trying to solve the same "puzzle" (aiming for the same target), but everyone is trying a different approach to do so (a different candidate block).
The target only changes every 2016 blocks (approximately every two weeks). So most of the time, you can know what the target will be after the next block: same as the current target. If the next block would be a multiple of 2016, then you will need to wait until it is mined, because its timestamp will be involved in the computation of the next target.