I would suggest making a header.php
file that contains the full header of your site, including the menu. Once you have done that, you can just call include("header.php");
on every page and your entire header will be brought in. This will also allow you to make one change in one file and affect the entire site.
To position the menu on the left or right, you are going to want to wrap the menu with a css call similar to float: left;
or float: right;
jsfiddlee: http://jsfiddle.net/jjS98/
here is the css code for floating your menu to the right:
#verticalmenu{
float:right;
}
You can change right to left for the desired results.