Ok, so you have a custom Magento theme (or at least a partially customised theme so far!), but now we need a custom search box.

In /app/design/frontend/your-theme/template, create catalogsearch/form.mini.phtml

<?php $helper =  $this->helper('catalogsearch'); ?>
<form id="search_mini_form" class="navbar-form navbar-right" role="search" action="<?= $helper->getResultUrl()?>" method="get">
    <div class="form-group">
        <div class="input-group">
            <span class="input-group-addon">
                <div class="glyphicon glyphicon-search pull-left"></div>
            <input id="search"
                   name="<?= $helper->getQueryParamName() ?>"
                   value="<?= $helper->getEscapedQueryText() ?>"
                   maxlength="<?= $helper->getMaxQueryLength();?>"
                   placeholder="<?= $this->__('Search...') ?>" />
                <span class="input-group-btn">
                    <button type="submit" class="btn btn-default">Submit</button>
    <div id="search_autocomplete" class="search-autocomplete"></div>
<script type="text/javascript">
    var searchForm = new Varien.searchForm('search_mini_form', 'search', '<?= $this->__('Search...') ?>');
    searchForm.initAutocomplete('<?= $helper->getSuggestUrl() ?>', 'search_autocomplete');

Of course, if you know how, you can generate a Zend_Form and save you having to code the form by hand! 😉