New Way:

Facebook is constantly changing its layout. The new way to disable public search is to go to

  • Account – > Privacy Settings
  • In the lower left hand corner look for Apps and Websites
  • Edit your settings
  • Edit settings for the public search
  • Uncheck enable public search.

Old Way:

Login to Facebook and go to your privacy settings.

Privacy  Settings

Select the Search Settings

Search Settings

Uncheck:  “Create a public search listing for me and submit it for search engine indexing”

Public Search Listing

Edit:  As Dan pointed out in the comments. Make sure  your Search Visibility  is set to everyone for the “Create a public search listing” option to show up.

It may take a week or more for search engines to completely remove your listing from their indexes. However Facebook is a popular site so I am sure it gets index quite frequently.