Image maps can be confusing.
A well order link list or nice navigation bar can be just as effective. If you do use an image map provide alternate text navigation.
Mouse overs can be almost as confusing as images maps if you don't do them properly. Make sure at least one of your mouse images is words.
Words are your friend on the web. They tell who, what, when, where, why and how. Sites that are one large image map with little blinking graphics for alternate navigation are worthless.
When naming the links on your site, try to use the KISS method. Some variation is good, it shows creativity and imagination. However, cute little names for each link can be confusing to the average web user. You have to tell them where they are going. Lead them. They will follow.
Underlined links I do not care for myself, but if you use text links with the decoration off make sure the user can distinguish them from the other text on your page.
Don't use frames just to show that you know how to use frames.
Web pages are small anyway, and carving it up with frames can reduce the usable area to a small part of the screen.
Most visitors have upgraded to browsers that support frames, if you believe the browsers stats, but what about the fellow who is still using the machine he got at the school auction. Do you just ignore him or do you maintain two versions of the same site?
Don't build your site around frames. It makes it difficult to navigate and limits you to having a very simple site. The cursor keys don't work unless you click in the frame you want to scroll, and the browser's 'Back' button may produce unexpected results.
Printing from a site that has frames can be an iffy business.
Bookmarking a special page of the framed site is not possible.
You may get unexpected results when a search engine indexes your site. Visitors who come to one of your pages from a search engine won't be entering through the site's front door and won't see the frame that would normally be holding the page. Which more than likely has the navigation on it, unless you were a conscientious soul and did alternate navigation.
Say your "framed" site has links to other sites, they show up within your frame, masking the identity of the other site and confusing visitors, who'll wonder where they really are. They won't be able to bookmark the linked-to site.
Plus, this may raise copyright issues if another site shows up within the frame of your site, which is certainly unfair to the other site.