Here are some resources for creating a custom theme in Drupal 6.
The minimum files you need are:
- .info file
- page.tpl.php file
- template.php file
- CSS stylesheet
The page.tpl.php file defines your HTML template. This is where you inject some PHP code into an HTML file to display the contents of your page. (See this .pdf for an overview of the various PHP snippets that are available). I've included a reference-page.tpl.php which includes all the different variables Drupal offers. You can copy and paste these variables, as needed, into your page.tpl.php file.
The template.php file will allow you to override some of the default functions of Drupal to help you display your content just as you want it. See my previous post on Drupal 6 template.php for some common and useful overrides.
It is considered a best practice to avoid inline CSS styling and separate all of your style definitions into another file. While some themes use several CSS files to manage different parts of the site, I've found that one master stylesheet is sufficient for me.
Finally, here is a zip file containing the elements aforementioned. Just unzip this folder to /sites/all/themes (create this directory if it does not already exist) and you should be ready to completely customize your own Drupal theme. If you decide to change the name of your theme, currently it is just theme, you need to update the name in the theme.info file, then rename the theme.info file to the_new_name_of_your_theme.info, then rename the folder to the new name of your theme, and also update the template.php file as I suggest in this blog post: Drupal 6 template.php.