How is the difficulty of bitcoin mining propagated? 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?
The difficulty is stored in the block in the Bits field. When any server receives a block, one of the things it does is check if the value in this field is correct. If it's not a block where the difficulty changes, it must have the same difficulty as the previous block. If it's a block where the difficulty changes, then it must have the correct difficulty according to the well known Bitcoin difficulty adjusting algorithm.

There is no "central bitcoin server".

Forks are resolved as follows:


Blocks that are invalid are ignored. Only block chains consisting entirely of valid blocks are considered.
The blockchain that would likely have taken the most effort to create (highest total difficulty) wins.