How are timestamps verified?
Actually Universign produces "Evidence Records" as described by RFC 4998. Evidence Records in turn rely on standard time stamps which RFC 3161 is about. Evidence Records can embed several nested time stamps; this is used for long-term archival, when you want time stamps to remain verifiable beyond the end-of-validity of the certificate of the time stamp authority, or even when one of the hash functions which were originally used becomes broken. Evidence Record Syntax (ERS) includes provision for regular maintenance, namely spraying a new layer of paint (a new time stamp) whenever needed.

As a general basis, a time stamping authority (TSA) works like this: it receives a document hash, and applies a digital signature on a structure which contains the hash value and the current date -- the date is measured by the TSA, not provided by the client. The signature, when verified, "proves" that the TSA was involved, and since we trust the TSA for having a well-maintained clock and never signing any structure for which it did not write the current date itself, this proves that the document hash existed since the announced date (at least). Hash functions being nominally impervious to preimages, this in turn demonstrates the existence of the document at that date.

The cornerstone of the trust is the "honesty" of the TSA, which, administratively speaking, goes through certifications. Various institutional bodies verify, through audits and procedures and mountains of paper which required whole forests to be cut down, that the TSA has been developed and is maintained with enough security, in a way which can be audited. In the case of Universign, they can boast such certifications as can be obtained from French government; in effect, France says: "their time stamps are good enough, that they can be used as proofs in legal proceedings, the burden of proof lying on whoever is arguing against the validity of said time stamps". This can be assumed to more or less extend to the rest of Europe, at least in the near future (the legal systems for electronic signatures and time stamps are slow to spread, but Europe is trying to push them in an harmonized way -- as always, things work differently in America, so the legal status of Universign timestamps in a US court is much less guaranteed).