From my understanding, it goes something like this:
1.The client creates a new block, containing the previous block's hash, the current outstanding transactions, and a nonce (among other things).
2. The client calculates the hash for this new block:
a) If it's less than the difficulty it publishes that block to all it's peers.
b) If it's above the difficulty it increments the nonce and tries again.
Verification is done by all the peers. They will only accept a block if it has the correct hash.
All the existing blocks are downloaded from the peers.