A couple of days ago I added a Google Search to my blog.
Here are a couple of helpful links on how to do it:
I ended up using #2.
This was one of the biggest things I missed at Blogger. (At the top of Blogspot.com blogs, you can search that blog which is great).