How do I change the page menu from being in the top of the page?
Please have a look at www.datingprofilessale.com. It just does not look pretty and/or professional.
I would like to have the page menu in the right hand column and I have no idea how to do that. Please be aware, I am a noob and my knowledge of WordPress is somewhere in between sketchy and non-existent.

I would build a menu with the WordPress menu builder (Appearance>Menus) and then use the Custom Menu widget to display it in the sidebar.