You could use the getXPathCount command to return the number of links on the page, and then loop through them using XPath. A simple example using Java with Selenium RC follows:
int linkCount = selenium.getXpathCount("/descendant::a").intValue();
for (int i = 0; i < linkCount; i++) {
    selenium.click("/descendant::a[" + i + "]");
    selenium.waitForPageToLoad("60000");
    //ADD YOUR CHECKS HERE
    selenium.goBack();
    selenium.waitForPageToLoad("60000");
}
If you're using Selenium 2 or WebDriver, the following should work:
List<WebElement> links = driver.findElements(By.xpath("/descendant::a"));
int lSize = links.size();
for (int l = 0; l < lSize; l++) {
    links = driver.findElements(By.xpath("/descendant::a"));
    WebElement link = links.get(l);
    link.click();
    //ADD YOUR CHECKS HERE
    driver.navigate().back();
}
Hope that helps.