Searching within Facebook and in your network of friends and friends of friends was an overdue feature.
So far, Facebook search has meant searching in the rather narrow field of people names within Facebook but outside a specific user's network of friends. Web search results (delivered by Bing) were also available often completely unrelated to the targeted Facebook search. Most FB users when searching within FB, clearly don't need to search on the web or they would simply switch to google or some other general-purpose search engine.
With FB's new "graph search", the search will be specific to the search user's network of friends (as far as the information has been shared with this specific user or with the public) and it won't only be about people's names. Indexed are also places, photos and any other clearly categorized information people put on their FB pages.
Still in beta for US users.
Update [March 15th]: Graph Search is rolling out very slowly. Will come back with examples when I have access to it. In the meantime, enjoy this as an intro to the tech behind it.