Adding a new region to your theme in Drupal 6
It's pretty simple to add a new region to your theme in Drupal 6. Most of this I gleaned off of http://drupal.org/node/134973.
First, if you don't have a custom theme yet and you want to work off one of the base themes, copy the appropriate theme's folder into your sites/all/themes folder, or if running a multi-site setup and you want this theme specific to your site, place it in the sites/<your site>/themes folder. To avoid confusion, we'll rename the theme. For my example, I'll use MyTheme. First, rename the copied folder to your theme name, such as mytheme. Inside the theme's folder, you'll find a <theme>.info file. Rename this file appropriately, such as mytheme.info. Edit this file, and change the property name to your theme name. That should get you your very own theme to work with. There's better and easier themes to start with, but google for those.
Now, in the .info file, add something like the following lines.
regions[left] = Left sidebar
regions[right] = Right sidebar
regions[content] = Content
regions[header] = Header
regions[footer] = Footer
regions[top] = Top
The first 5 lines are the original regions that we don't want to lose (or maybe you do), and the last line is the new region that you want. This overwrites the region array internally (hence why we have to add the originals). I've chosen a region called top, as I wanted a block to go on top of the content region to display a banner ad (sorry people).
Next, edit the page.tpl.php file, and add calls to display your region where you want, such as
<?php print $top ?>
I've added mine right above the call to print the content - </?php print $content ?>.
Go to Administer->Site Building->Themes. If you haven't changed your site to use your new theme, choose your theme now, otherwise hit the save configuration button to reset the theme cache and load your changes in.
Going to the Blocks editor, you should now see your new region appear and able to move blocks into it.