The Menu is populated by databinding to the SiteMapProvider via the SiteMapDataSource control. The SiteMapDataSource control lives in the layout.master file of the skin. The actual data binding happens in SiteMenu.cs which is in the Controls folder in the code.
In the databinding event pages are filtered from the menu by role so users only get to see pages for which they have permission.
Yes different skins can have either horizontal or vertical menu. Example skins with horizontal menu are IBuySpy, mojoguidetogalaxy
You could assign a different skin to the pages where you want a different orientation. Another option is to use a horizontal site menu and a vertical page menu as seen in the skins named jwh1, treeview2, splitmenu1, and splitmenu2. This works well as sub pages below the top level are shown vertically in a different menu.
studying the layout.master and the style.css files for existing skins should help you. It is also very helpful to get a good CSS reference book.
Hope it helps,
Joe