The interesting thing about Facebook's announcement, though, is how they're choosing to attack the problem. To understand why this can completely disrupt the search market, let's quickly look at how search got here.
When Google broke onto the scene in the late 1990s, the default way to organize information on the web was through directories. Yahoo and others invested huge effort in creating large sets of categories and tried to fit all the links on the internet into these categories. And when Google came along with its single search box that could search over everything, it was a much better experience.
The information paradigm shifted from looking through directories to searching by keyword. Google has, over the last decade, built up a huge amount of data that makes it nearly impossible for anyone to compete with Google directly on search. The only way to get ahead of Google is to get to the next evolution of the paradigm.
It's been long speculated that the natural next step for information retrieval on the internet will be recommendations. Search today just returns relevant results, and leaves it up to the user to make decisions. For example, if you were looking to go out for dinner today, you'd search for "Restaurants near Indiranagar" (tell us hi here!), and sort through the results and decide where you want to go. But what you really want is to ask "Where should I eat tonight", and it comes back with a recommendation, incorporating your personal preferences, what you ate last week, and how much money you usually spend on a Saturday night dinner out!
To make these kinds of recommendations work, you need a lot of personal data. Amazon has had a head start here, using the tons of shopping data it has to be recommendations, but these are also rudimentary. Google has been trying to get more and more of your personal data for years, so it can start making personalized recommendations.
Facebook has had all these data for a while now, and now is getting into the "search" business. But this is not the traditional search, it is more a recommendations engine, that will suggest what you should do. Feel like a ski holiday? Facebook can recommend friends that you can take with you. Want to buy a new Jacket? Facebook can figure out the friends who's fashion opinion you value, see what they are wearing this season, and recommend it to you.
This paradigm is interesting not just to users, for whom it is more convenient, but also to the advertisers. Advertisers will no longer be satisfied just appearing alongside results and hoping you click on them. They want to be more aggressive, be more a part of your lives and influence the decision making process. It is easy to see a Fashion retailer "working" with Facebook to influence recommendations for clothes.
There are lots of legal and privacy issues to figure out, but as technology and products gets more integrated (read invasive) into our lives, this is the next step that all the internet biggies - Amazon, Facebook, Microsoft and Google - will pursue. As usual, the privacy nuts will oppose this tooth and nail, but in the end, the users will chose convenience over privacy.
Graph search is Facebook's first serious attempt at getting into this game. Expect Google to retaliate with a recommendations offering of its own.