You don't have to copy every file. It will only confuse matters when you upgrade/update. Only copy the files you need to change. Stevesh's suggestion isn't a bad one, although I've never done it quite that way.

In addition to the header.php file you created, you'll need to create includes/templates/YOUR_TEMPLATE/template_info.php. You can copy any template_info.php file that came with Zen Cart into your custom folder and edit it there. It's a small file. Give your template a name you'll recognize when you go into your admin. Under admin->tools->template selection, you can select your template and after doing that, you should see the changes you made on your site.