If you haven't done it already copy newsletter.xml from here:
/app/design/frontend/base/default/layout/newsletter.xml
to here:
app/design/frontend/default/your theme/layout/newsletter.xml
Now there are a couple of options…
1. To move it from the left to the right change the name reference to 'right':
<default>
<!– Mage_Newsletter –>
<reference name="right">
<block type="newsletter/subscribe" name="right.newsletter" template="newsletter/subscribe.phtml"/>
</reference>
</default>
2. To move it to the header or footer change the name reference to header or footer, then in the template file call it by adding this:
<?php echo $this->getChildHtml('header.newsletter') ?> to move block newsletter to header
<?php echo $this->getChildHtml('footer.newsletter') ?> to move block
