So it turns out there are a couple ways to do this. It depends on what kind of search you want for your blog. Actually, you can even go as far as setting up a Google Custom Search for your blog, like we used to use, but these are a bit simpler and faster to set up.
First, you've probably seen the search box on the Blogger navbar.
By my guess, this is probably in the source code of all or most Blogger templates, but I know for a fact that some of them hide the bar (it's actually an iframe if you want to know), such as our template, Subtlebeauty. You'll have to remove some code from your template if it's hidden on yours and you want it to show. For example, in Subtlebeauty, I'd probably remove the lines:
#navbar-iframe {
height:0px;
visibility:hidden;
display:none;
}
Check out this page for a full tutorial on how to remove the bar (possibly because it looks terrible with your theme or you're using a different search box). If you want to change the color scheme of the bar (there's only 4 available), check out this page.
The second way is maybe a little easier. It's pretty much the same search as the navbar provides, just using your own search box, which means you can put it wherever you want on your blog. Head over here and grab the code or press the Add To My Blogger button. You can change the text displayed when the search box is not being used and the text on the search button as described over there. Just take a look at the code and you'll probably get it. Easy as pie. In fact, I put the code in below so you can test it out right here.
And the third way is a piece of cake. It's the new Blogger Search Box. Quote from Blogger Buzz: "To add the gadget, go to your blog's Layout page, then click “Add a Gadget” and click on “Search Box.” Super easy, and it has some cool options. It's a lot more advanced than the previous two (but just as easy to use). It used to only be in Blogger in Draft, but now it's public, so woot woot!