There are a couple of ways you can do this in Magento. There may also be any other methods with some modules or so other than what is listed below. Here a few ways that I normally use.
Find page/html/head.phtml in your theme and add the code directly to page.html.
page.xml - you can add something like
If you check the stock page.html mentioned above, you can see this line
<?php echo $this->getChildHtml() ?>
In normal cases, the getChildHtml method is used to render a specific child block. But, if this is called with no other paramaters, then getChildHtml will automatically render all the child blocks available. Which also means you can add something like
<!-- existing line -->
<block type="page/html_head" name="head" as="head">
<!-- new sub-block you're adding -->
<block type="core/template" name="mynewtemplate" as="mynewtemplate" template="page/mynewtemplate.phtml"/>...
to page.xml, and then add the mynewtemplate.phtml file.
Any block added to the head block will be automatically rendered. (this automatic rendering process does not apply for all layout blocks, only for blocks where getChildHtml is called without paramaters) as mentioned above.