Do miners have to start over whenever a block is found? If I understand correctly, each miner selects a set of pending transactions, puts them in a block, and then tries to sign that block. Pooled miners do the same, but the specific set of transactions is selected by the pool server.  

Since each block must link to the previous one, does it mean that whenever a new block is found (by another miner) the whole process must start over?
In a sense, yes.

However as the mining process is essentially guessing the right number from a very large set of possibilities it's misleading to say you start the process again as you're just as likely to guess the next block first try as you are to have guessed the previous block. You basically start the process each "guess" anyway, whether you try again on the same block or start trying a new one is of little consequence.

You could very well find a new block the very second after you accept a block. In that case, you wouldn't have found a block if you had kept mining on the old block.