Let's say the current difficulty is set as finding a hash with 4 leading zeroes; once this is found, a block with this hash is propagated. Every client that receives this block checks that it has 4 leading zeroes and accepts this block as valid, adding it to their own chain.
My understanding is that the only information a miner sends out, when he solves his hash, is this block he has created (containing the solved hash and details of all the transactions that he used when creating the hash). This information, and only this information, then propagates to the rest of the network.
Now, how does the "central bitcoin server", or whatever it is, then propagates the change in difficulty every 2 weeks? Would it require everybody to update their client software to recognize that new blocks are only valid if they now have 5 leading zeroes, or is there some genius mechanism that I'm missing? On a side note, I don't really understand how forks are resolved; is this relevant to how this issue is dealt with?