I saw people recommending to make the changes in tpl_header.php and they showed changes to <td> tags, but I didn't see any <td> tags in the document.
Beginning with 1.3.x and a template based on the single stylesheet.css of the template_default fileset; there are very few TD tags and have been replaced mostly with DIV's.

To center the logo: In your stylesheet.css file locate the #logo and separate it into it's own entry. Find this:
Code:
#logo, .centerBoxContents, .specialsListBoxContents, .categoryListBoxContents, .centerBoxContentsAlsoPurch, .attribImg {
	float: left;
	}
Pull #logo out into a separate entry like:
Code:
#logo {
        text-align: center;
        }
 
.centerBoxContents, .specialsListBoxContents, .categoryListBoxContents, .centerBoxContentsAlsoPurch, .attribImg {
        float: left 
        }