By their account, if you search something (A) and then you search something else (B), there is no way to link A and B. They are two separate searches and they could have been performed by separate users.
Granted, given a ton of disparate searches, you could theoretically group searches by possible users — or at the very least, by similar users — by statistical means.
(Edit: Actually, now that I think about it, while they mention timestamps in terms of other search engines, they do not mention their own policy regarding them. Timestamps are not directly “identifying information” but they still significantly boost the likelihood that a specific user is performing a given set of searches.)
But I can imagine the benefits of keeping track of all searches done by one user. It can definitely be used to improve the search engine itself.
I understand that that they do not store IP address/cookie/etc, but often by just looking at as little as a few searches you can zero down on the person in question. For example I have often searched for:
Citrix Blogvault
I am possibly the only person who will be searching for both those things.