There is some information related to your question here and on other questions on StackExchange.
I theorize that as the general public becomes more attuned to working with the internet and getting information from it, we increasingly know exactly what we want and we are getting better at getting the information we want with the least amount of effort. It's possible that Facebook's move from browse to search reflects that.
One of the problems with classical browse is that it requires a structure, typically a hierarchical one. Once a hierarchical structure is in place, and content has been created to suit it, structures tend to become static and resist change. Implementing a good browse navigation requires that you get into the heads of your users, and it requires significant planning ahead, especially for content that you do not yet have but plan to include in the future.
From the side of the users, a danger with a reliance on browse-only navigation is that it forces them to guess what abstract topic best fits their area of interest so they can access the right high-level node and drill down. This abstraction process can be cognitively demanding on users (first-time visitors to your site in particular) and depending on the situation may cause frustration.
One of the most popular browsable content trees I am aware of is dmoz (link here). This site is great if you have no precise information in mind that you are looking for but are really in the mood for free discovery.
Search functionality addresses these drawbacks but makes it harder to explore new things, so as others have said it both methods have their usefulness. A drawback of targeted search is synonyms - if you have a page called "order history" and you have a visitor who is not native English speaking and searches for a "purchase log" (essentially the same thing) they may be out of luck.
I think Wikipedia have done a great job combining targeted search and free discovery. They do this with classical search that brings you to the appropriate page, and on the page you find links to related information that may be organized into "portals" or "hubs" or "projects". The advantage to the "search and hub" combination is that you can search AND you can browse but you aren't forced into one overarching hierarchy.
This makes browsing more dynamic and it reduces the amount of planning ahead that is required to implement it.