New regions?

The search box works fine for me... did you remember to activate it in your theme settings ?
The regions are not set in the info file because it just uses the default drupal regions. To add new regions, you have to declare the default ones and add your custom one. And remember that when you change your info file, you have to refresh your theme cache by just submitting the theme page.

Create a new region in Drupal 6

It is done in two steps. First you need to declare the region in the .info file, and then you need to assign it in your page.tpl.php.

To declare a region in the info file, for example a "content bottom" region, add this in your info file :

regions[content_bottom] = Content Bottom

The first value is the machine readable name of the region, and the second one is the human readable name, that will appear in the drop-downs on the block page.

Now that the region is declared, you have to specify where in the page the region should be. To do this, you just have to add the variable to the page, using the machine readable name you created, like this :

<?php echo $content_bottom; ?>

A good idea would be to only output the region if there is something inside it, so create a condition that check if there is something in the region before outputing it, like this :

<?php if ($content_bottom): ?>
  <?php echo $content_bottom; ?>
<?php endif; ?>

You can even add some markup around it (but inside the condition), to theme it easily :

<?php if ($content_bottom): ?>
  <div id="content-bottom">
    <?php echo $content_bottom; ?>
  </div>
<?php endif; ?>

There you go !