Your basic structure would be a div with a header followed by an unordered list:
<div id="mainnav">
<h2 class="hidden">Main Menu</h2>
<ul id="nav">
<li><a href="/home.html">Home</a></li>
<li><a href="/about-us.html">About Us</a></li>
<li><a href="/services.html">Services</a></li>
</ul>
</div>
The header is very useful for screen readers and can be hidden from visual users. The best way to hide information from sight while still having it accessible to screen readers is to use absolute positioning off the screen.
hidden.h2 {position:absolute; margin-left: -9000;}
or
hidden.h2 {position:absolute; top:auto; left: -9000;}
For a menu to be useable to anyone using a keyboard rather than a mouse, make sure that if you use :hover to initate any actions, also initiate the action with :focus. One difficulty here is that while :hover engages parents and children, :focus only looks at the specific element.
Along the same lines, if you use Javascript, make sure that anything that can be done by a mouse can also be done via the keyboard. If you use onmouseover/onmouseout you also need onfocus and onblur plus alternative text. Using onclick is fine as long as the Enter key can be pressed when the link has focus.
Another usability feature is to have the entire area clickable, not just the anchor text itself. Using display:block with padding will accomplish this:
a {display:block; padding: .5em;}
The path to making a web site truly accessible is a continuing process. You can make a start by adding some of these techniques to your normal routine.
For more information see the WebAim web site for techniques to use to help bring accessibility to the internet.
Another site with working menus is Matt Carroll's version of Son of Suckerfish.
