To customize the layout (eg for this sites form) we just edit the css files in a themes/themename/css/Form.css. If you have a Form.css it will override all the default styles.
To get it on the right simply float the button right and float the input left. Or use css positioning. I tend to avoid trying to mess with the form templates / markup as most designs can be done with CSS.
Use a tool like Firebug to work out whats happening. Could be not loading your styles, could be getting overridden. Looking at that if #Search is your search box then it needs to be wide enough for the input + the button. Also #Search_Form_SearchForm_Search would need to be floated left (since otherwise it would push the action down).
See this page for some more information on how to use css positioning http://www.barelyfitz.com/screencast/html-training/css/positioning/