ok mira, imagino que ya tienes la imagen que quieres ponerle al menu cuando lo visiten, lo unico que hay que hacer mediante css (es indiferente si es hoja de estylo aparte o esta en la misma, aunque recomiendo la primera) es decirle al link que cuando lo visiten, cargue una imagen de fondo en el div o el li que lo contiene
algo asi
Código HTML:
a:visited { padding-right: 12px; background: url(visitedLink.gif) no-repeat 100% 50%; }
en el caso de mi menu, simplemente va que cuando este activo, cambie el color de fondo del <li>