That doesn't actually work in pretty much any browser, since it allows for history-mining by a malicious site. :visited styling changed a couple of years ago to only honor color changes, thus preventing most ways of exploiting that issue.
I guess you could create the triangle solely with CSS borders, and then style the border-color to be the same color as the background when not :visited
make the "upvote" buttons invisible on stories that the user hasn't visited before. This could be done like so:
The href & onclick handlers would need to be added in javascript so as not to affect hn for non-js users.