There are no rules, at least no hard and fast ones. Following research to the letter can result in making an ugly site--blue links work best, but blue links on a red background are hard to read! The research however can guide you to the "best practices" and your maintain your sense of good aesthetics so you know when to break from convention.
While there are no rules, there are lots of guidelines; some outdated and some very good.
The old standby for link appearance is Nielson's Alertbox posts:
Visualizing Links and Change the Color of Visited Links
People get lost and move in circles when websites use the same link color for visited and new destinations. To reduce navigational confusion, select different colors for the two types of links.
These posts give a good basic summary, but they're quite old. The big thing to take away is that links should be a unique, consistently chosen color and visited links should be a clearly different and consistently chosen color. Don't put too much stock in the statistics however as the web has changed a lot in 7 short years. We'll get to current stats next.
Probably the single most important piece of research on links is a Google experiment showing blue links are clicked more. Non-blue links are clicked less, so one's color scheme should take this into account. Blue should be avoided for body copy due to this, as should underlining.
As for visited links, here's a great, up to date article on the state of visited links on the web by Kevin Simons; Where Have All the Visited Links Gone?
Simons notes that visited link color use has dropped sharply--I'd go so far as to say in 2004 most sites probably just never bothered to style their links, resulting in the default visited link color change. Simons points out the main use of visited links is to help a user keep track of where you've been:
Specifically, pay attention to the cognitive effort you have to expend on sites without a visited link color, just to keep track of where you’ve been. You’re sure to develop a renewed appreciation for the visited link.
Does the user need a reminder that they've already navigated to this link? If they don't, the link style probably shouldn't change at all. Note that for top level navigation elements a visited link color may be unnecessary and visually ugly (do I really need to visually SEE that I've never used the Contact Us section?).
For dynamic pages, a visited link color may be downright misleading; many web apps today have dropped the visited link convention as "visited" doesn't mean much in the context of an application or dynamic pages.
If you do need to make a distinction between visited and unvisited links, Contrast is King.
As Leslie Jensen-Inman from A List Apart notes:
Using contrast effectively not only differentiates your design from others, it’s the essential ingredient that makes content accessible to every viewer.
The article goes into good detail of how contrast is important and how to use contrast effectively; I strongly suggest you give it a careful read.
They note that for accessibility reasons you should check your colors against common colorblindness simulators to make sure the contrast is suitible for colorblind users as well as non-colorblind users. Consider daltonizing your colors to see if they work better.
They also bring up CheckMyColors.com, a great site which will allow you to check the background/foreground contrast of all elements of your site at once.
Note that foreground/background contrast will not tell you whether two foreground bits of text have enough contrast! This is why you can't just use the Color Contrast Checker like some have suggested and call it a done deal.
Here's a great guide on Typographic Contrast which will help you put together all forms of contrast to make a nice flowing site.
Bottom line, contrast is great to differentiate things but it should be used appropriately. If there's really no reason to differentiate links that are visited and not visited, don't. If maximum contrast or standard link colors are too ugly with your current design, try something different.
Only real users can check if your links are distinct and functional.