They should start charging Google to index their content, not the readers. If I were an advertiser on nytimes.com I would be livid right about now.
Why would Google pay? There's very little in the NYT that is unique. How may people would switch to another search engine if Google ignored the NYT?
Google delivers eyeballs for free. The NYT is free to monetize said eyeballs as it sees fit.