Which one do I do my changes to??
None of the above. Since, by doing so, you will alter the template_default's readings once the next releases will be pulished from the DEV Team. Please read the FAQs and wiki documentation regarding templates overrides.
The above should read like this:
/public_html/shop/includes/templates/
I have two choices:
<your_template> and
common
So, techicly;
PHP Code:
/public_html/shop/includes/templates/<your_template>/common/tpl_header.php
Do NOT use the template_default folder.