Something you would want to consider for "menus" not created by the Core menu system is generating any links you create with the l() function http://api.drupal.org/api/drupal/includes%21common.inc/function/l/7
This means that at the least Drupal will add the "active" class to links that take you to the current page which can be essential for theming them properly.
Generally I'd say you should create a render array (or arrays) and get drupal go generate all the markup you need from that, but it sounds like you might be a bit too new to Drupal to be doing that.
The idea of wrapping menus in a list (ul) structure is totally optional, don't feel obligated to do it just because you've seen it elsewhere. It can help if you're doing things like drop-down menus or similar but don't worry about it magically boosting your SEO or that other people know something you don't.
You probably do want to wrap each item in some kind of html tag to help with theming, but that could just be a span/div.
One interesting idea to consider is a single table row as it will automatically space words out for you in a way that's difficult to do with other markup - but whether this helps or hinders is entirely dependant on the design you're trying to implement.