The way I would get something like a search bar on every page is to add a new "Search" block via the "Page Type Defaults" found in the "Pages and Themes" section of the dashboard.

Use one of the default Concrete themes and go to the Dashboard. Select Pages and Themes. Then select Page Types. You'll see a list of all the page types being used for that theme.

I would start with the Left Sidebar page type and click on the "defaults" button. Edit this page the way you would edit an existing page in the site, but after adding a block (like Search) click on it and choose "setup on child pages." This will push those additions to existing pages that are using the Left Sidebar page type.

However, what's cool is any new pages you add using the Left Sidebar page type design will also automatically contain those blocks you added in "defaults."

I think this will help you figure out how to get the search bar on all your pages -
assuming you want the search bar on top or below the nav.

Getting them side-by-side is another discussion...