Your best bet for a search box is a widget. Head over to Appearance – Widgets, then find the Search Widget and drag it into the sidebar (top position looks best I find).
You could do the same with the Archives widget. Also look into the P2 Recent Tags widget, which will display the last xx used tags in the sidebar, nicely formatted. Clicking on such a tag will generate a tags archive page.