As someone mentioned in stundubl's thread in Supporters, Google directory still shows PR ranking, however in the link dev scenario, not every site is in DMOZ, so we'll still have to do some basic quality checks.
Many people will know all this, but maybe some don't so I'm going to lay this down for those who may find it helpful:
The first check is to verify if the potential link partner is banned. So you go to Google and query the domain name, domain-name.com or www.domain-name.com and if the answer is "Sorry, no information is available for the URL domain-name.com" then you've got a problem site. Back away.
If it passes the first test then go to Yahoo and do a backlink check. Check out who is linking to it, and how many are linking to it. Quantity is going to be one signal of quality.
Do a whois search and check out what country it's regged in, when it was regged, who it's regged to, and in some systems you can even see all the other websites sitting on the server or else determine if the site is on a dedicated ip. Also, some systems allow you to check the ownership history going back several years, which is good for smoking out an expired domain, but otherwise you'll have to go to the next step.
Archive.org history search. This is a good way to check if the site in question is an expired domain.
There are probably loads more checks you can do. Anyone else care to add?