Section 4 of the linked paper answers some of your questions:

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash, rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash.
For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

1. The 'server' publishes blocks of data with a hash digest.
2. The previous hash is included in each block, as illustrated in section 4 (not included above).
3. It is published to all connected P2P nodes. Section 5 of the paper goes into a little more detail.

Section 4 of the linked paper answers some of your questions:

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hashcash, rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash.
For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

1. The 'server' publishes blocks of data with a hash digest.
2. The previous hash is included in each block, as illustrated in section 4 (not included above).
3. It is published to all connected P2P nodes. Section 5 of the paper goes into a little more detail.
4. OriginStamp uses several blockchains to timestamp documents. Zoho provide a similar paid service. OpenTimestamps is free and relies on donations. Naturally examples of such timestamp services are built on existing cryptocurrency blockchains.