How you add the list HTML depends on whether you're using absolute or relative positioning (for these purposes, if you're using popup menus that counts as absolute positioning). If you're not sure what kind of positioning to use, please see Choosing a positioning mode.
You can put a relatively-positioned navbar inside one or more containing elements, and position or float those as you need. You can also have an absolutely-positioned navbar inside a relatively-positioned container, and if you do then it's x, y co-ordinates will be from the origin of the container. I don't recommend that if you're using fixed positioning - the end result will be very different between browsers.
If the navbar is anywhere except the very end of the source code, you'll need some kind of "skip" link.
UDM 4 is valid XHTML, and in our judgement, meets the criteria for WAI Triple-A conformance.