Initial thought: "thank heavens they're fixing the search function, it sucks beyond the telling."
Facebook, sensibly, are restricting their search space to Facebook itself, plus shared content. Presumably they will crawl external pages that users share, index significant terms, and allow Facebook Search (hereafter FBS) to direct users to the shared page. Their indexing task is therefore relatively predictable; they just have to index each post/album annotation/check-in as it is made. Since these are small text items, it's not a massive incremental burden to bear.
The interesting part is the privacy aspect:
Search is not a massive change for FB. All that they are doing is making the Search: bar work reasonably well, by which I mean "much, much better than currently", plus doing some natural language processing on queries to identify significant entities (places people check-in, user friend names and transitive relationships.) The interesting question for shareholders is "how does FBS add to the bottom line." It's not obvious, which is why FB stock dropped 2.74% after the announcement.
The Search function could occupy a lot of FB CPU time. As an active FB user, at best I'd use search 2 days a week. If there are 500 million active FB users, which is an over-estimate, that's 1bn FBS queries per week - or 1600 searches per second. That's a lot of hardware that FB will have to devote to searching; for something that has no obvious commercial value, it's a big drain on FB resources. Since Google does 4.7b searches per day, Facebook will have to build out 3% of Google's search hardware just to service these queries. Google has about 900,000 servers, so Facebook needs 27,000 additional servers (plus power and networking infrastructure) for no obvious financial return.
Time to sell FB? I think so. (Disclaimer: I do not hold FB stock, or any options on it; do your own diligence; if you take investment advice from a pseudonymous blog then you must be nuts.)