Hi,
If you place the control you mentioned above your main menu inside the layout.Master file in your skin, the search box should appear above your main menu. You may have to add style to your skin to make this look the way you w ant it to, but it will render the markup in the right order. What problem did you run into with this specifically?
As for searching, if you go to the /searchresults.aspx page on any mojoPortal site you should see a small "help" question mark somewhere around the search options (visuals depend in the skin). If you click that, it will pop up and tell you how you can perform fuzzy searches. In this case, if you typed "cons*" the search would return all matching words that start with the string "cons", like "consequence" or "consistent". If you typed "cons~" it would return all matching words that have any sub-arrangement of the characters in the word "cons", for instance "icons", or even "cols" (because "co" is a sub-arrangement). We don't think this behavior should be automatic for half-typed words because some sites are very large, and fuzzy searches would result in thousands of pages of results with no guarantee that they are very relevant.
Hope this helps!