Okay, I'm revisiting this topic because I dug and experimented till I found some viable options. This is a little sad, but on a Saturday night, I am at home, on the verge of a happy dance because I found one that works for me (at least until SD creates a built-in one).
Anyway, this website lists several reliable sites that offer code for creating a pretty respectable (clean, easy) search function in your SD shop.
http://www.javascriptkit.com/howto/search.shtmlI chose the second site, the one they recommended, signed up for a free account, then pasted the javascript they provided in the "title" box of a new info page in my SD shop. The body of the info page can't be blank, so I just pasted the code there, too. So when I look at my shop, the search bar shows up by my pages (Returns, Shipping, Payment, etc.). I am SO excited that I wanted to share this!!!
p.s. don't be like me and freak out when the code doesn't seem to work immediately. The site needs time to crawl and index your shop before the search works :o)
Hope someone else gets something out of this- I feel like I'm making progress!!!