How to 'Show a graphic tick, in a visited link'?

That would depend on the menu you are using (assuming it is a CSSMenuWriter menu). Some already use background images for normal and hover states, so adding a tick image wouldn't work on those without a clear understanding of how the (usually three) bg images were styled.

It would be fairly straight forward to add a tick as a background image to the visited style of a menu item that did not already have a background image:

[element_name] a:visited {
    /* your existing styles */
    background-image: url(images/tick.png);
    background-repeat: no-repeat;
    background-position: right center;    
}

That would display the image at the right. Your list menu would obviously need to be wide enough to accomodate it and clear the link text. You could add a padding-right:XXpx to the element the same width as the tick image if you wanted to make sure the link text didn't overlap the tick image.

This would need to be done after the CSSMenuWriter has done its job, otherwise you could lose the changes.