Your first paragraph isn't quite right. There have been cryptographic proof-of-timestamp systems for a long time, and they're described in standard crypto texts like Schneier's.

They work basically the same way, except that you have to set up your own network. When you want to timestamp something, you (just like this service) hash it together with the previous entry in the system, sign it, and publish that. The proof of the timestamp lies in how you had to look at the previous entry to make it, and the next, at yours. Compromising it would require a large number of participants to cooperate to re-write the history (and the participants' own records).

What this service does is avoid the need to integrate with an existing service or pay any of the record-keeping costs yourself, and it does so by piggy-backing off of bitcoin's distributed timestamp system, thereby making your timestamps at least as valid as bitcoin's, and increasing (significantly) the number of conspirators required to falsify it.

tl;dr: This is just like existing crypto timestamp systems except for the more extreme decentralization and using the bitcoin network's resources.