Para cambiar el color de los links visitados usas la pseudo-clase :visited. Lo usas sobre el selector "a" de los enlaces.
/* Estilo para enlaces visitados */
a:visited {
color: purple;
}
Por supuesto, para que se vea el cambio de color los enlaces normales deben tener un color distinto:
/* Estilo por defecto para enlaces */
a {
color: blue;
}
La pseudoclase :visited no permite cambiar cualquier tipo de estilo para evitar que el layout de una página se modifique dependiendo de si ha visitado algo o no.