Frustrated with the lack of Google's Search on the Samsung Fascinate? Here's a quick step by step to remove it:
Download the attached file: EnhancedGoogleSearchProvider.apk
Place the file on your SD card, and install it through your favorite file manager.
In a third-party launcher (like ADW or Launcher Pro), put the Google search widget back on your home screen, if you like. It'll work now.
Same goes for the search button. Again, you have to use a third-party launcher.
You'll still need to download Google Maps from the market if you haven't already.
Source: Here's your Verizon Fascinate Google search fix (update with even more fixed) | Android Central