Check out the siteowner page for details on how to add either a "Basic" search box that adds a Windows Live Search box to your page with html, and sends search results to the Windows Live Search page, or an "Advanced" box that creates floating <div> tags to display the search results right on your site.
There's some more information on the Live Search blog. Too bad Scoble can't use it, it looks kinda cool. We may be playing with it a bit here in the coming days, stay tuned.