are you building your menu with categories, or with pages? If with categories, you'll need a category sorting plugin
http://wordpress.org/extend/plugins/my-category-order/. If pages, just use the page numbering system.
Your adsense - just use a text widget and paste in the code.