Check out the file here: http://josiah.ritchietribe.net/blog/menu.phps
You can see it in action on my menu at: http://josiah.ritchietribe.net/blog/
It is my menu code (I insert it into index.php so it is really part of that file.) You will notice lines like
<?php wp_get_links(2) ?> The 2 indicates the second category. You can do a separate call for each category. You can also use the code
><?php echo get_linkcatname(2) ?> to retrieve the name of the category from the database. Again, change the number for the category that you want. You'll notice that I follow the default menu organization of xhtml lists to organize my categories. You are welcome to copy the file to get you started if you wish.
Hope this help you out.