Themes

You can have a separate theme for the front end and the back office, but by default the theme is used for both aspects. Go to Administer -> Site configuration -> Administration theme to configure this.

When developping a theme, add the following function to your theme template.php file to flush the theme registry (apparently needed):

drupal_rebuild_theme_registry();

Adding regions to Themes

This is done in the theme's .info file. After that you can assign blocks to these regions; the region should be outputted in the theme's page.tpl.php file (via print $regionname).
Note that when JavaScript is active, the Weight field is not displayed in the Blocks administration page (you can drag & drop via JS to change the weight). It is displayed when JS is not enabled or the scripts are not loaded, so don't be surprised.

Normally each module should register some theme hooks, which basically means that their output can be changed by themes (a default output should be provided as well). This can be done via a function (default) or the use of a template file. Some common registration are found in the common.inc file, for example a registration for the theme_links function.
For a template file, you have a preprocess function that can perform some logic before passing data to the template.
For more information look at this link or this one.
When looking for the default function for a theme function override, use the name of the function preceded by theme. For instance theme_menu_tree; never touch menu_tree directly.

Customizing menus is incredibly difficult in Drupal because the APIs are stupid and don't send enough information to the theme level overriden function. For instance theme_menu_item does not send any details about the level of the item, its parent, etc. If the core is left untouched (which should normally be always the case), the only way to really theme the menus is to use lots of regular expressions on theme_menu_tree (and theme_menu_item) to radically alter the produced HTML.
Other solutions (except core hacking) include:
- use of modules / plugins (not yet investigated yet);
- restrict links to one level, which make it easier to theme (as you don't have to deal with levels).