Editá el archivo header.php y ubicá esto donde quieras el formulario:
Sólo como nota aparte, esto podría ser un poco más complejo en un theme muy desarrollado pues tienen muchas funciones personalizadas y muchos más archivos.
http://codex.wordpress.org/Function_...et_search_form