How do I get a paginated view to display rel="next/previous" tags?
You just need to override theme_pager_previous() and theme_pager_next() (easiest to do in your theme):

function MYTHEME_pager_previous($vars) {
  $text = $variables['text'];
  $element = $variables['element'];
  $interval = $variables['interval'];
  $parameters = $variables['parameters'];
  global $pager_page_array;
  $output = '';

  // If we are anywhere but the first page
  if ($pager_page_array[$element] &gt; 0) {
    $page_new = pager_load_array($pager_page_array[$element] - $interval, $element, $pager_page_array);

    // Changes from core function start here.
    $attributes = array('rel' =&gt; 'prev');

    // If the previous page is the first page, mark the link as such.
    if ($page_new[$element] == 0) {
      $output = theme('pager_first', array('text' =&gt; $text, 'element' =&gt; $element, 'parameters' =&gt; $parameters, 'attributes' =&gt; $attributes));
    }
    // The previous page is not the first page.
    else {
      $output = theme('pager_link', array('text' =&gt; $text, 'page_new' =&gt; $page_new, 'element' =&gt; $element, 'parameters' =&gt; $parameters, 'attributes' =&gt; $attributes));
    }
  }

  return $output;
}


And the same thing for pager_next.