Today I needed to add a new candidate page.tpl file based on node-type. I found this code snippet and modified it slightly.

function phptemplate_preprocess(&$vars, $hook) {
	switch ($hook){
		case 'page':
		  // Add a content-type page template in second to last.	
			if ('node' == arg(0)) {
				$node_template = array_pop($vars['template_files']);
				$vars['template_files'][]  = 'page-' . $vars['node']->type;
				$vars['template_files'][]  = $node_template;
			}
			break;
	}
	return $vars;
}

My tweak puts the new template in the middle of the candidate templates array so that I can still have specific page.tpl files for specific nodes. The devel module tells me my candidate files are now:

page-node-4.tpl.php < page-story.tpl.php < page-node.tpl.php < page.tpl.php

This works on Drupal 6.