You can now add search to your site with the Live Search Box.
Live Search Blog: "Add Search to Your Site with the Live Search Box".
The search box comes in two flavors; one that displays results on the Live Search results page and the other that displays results right on your site.
You can get started on the Live Search Box site. I'll be tinkering with it later on tonight.