I'm new to drupal and a bit confused by this. Using the standard Bartik theme (Drupal install 7.8) I see a search bar on the sidebar. Checking the Structure > Block it shows that the search is included in the Bartik theme on the sidebar. The preview while an admin shows the search.
However, as soon as I log out the entire sidebar_first region does not show. Just the content area.
EDIT: When adding a login box to the sidebar it does appear, however, the searchbar, and navigation do not. There are NO RESTRICTIONS applied.
EDIT2: View the screenshots below to see my settings.
Normal User sees:
Admin User sees:
Current settings for navigation block: