They prove that the hash they publish in the NYTimes exists at that time. There are probably some archives which can give you an authorized copy of the NYTimes from a specific date. You can use that to prove that the hash existed at the date the NYTimes was published. This is now the hash over a hash tree, which this companies stores. With this single hash they can also prove that every document in this hash tree existed at that time. They can not add a extra document later, because this would alter the hash they published in the NYTimes.

When you publish your phony ad in the NYTimes, you also prove that this phony ad existed at the date the NYTimes was published.

This company probably buys one edition of the NYTimes with their add and check if the NYTimes published the correct hash, if it is wrong they will run an other add the next day with the correct hash the next day. Now they only prove that the hash existed the next day.