Волнующий вопрос! К сожалению, сейчас нет хорошего способа сделать это.

Подчёркивание через border-bottom позволяет управлять цветом и стилем линии, но не её позицией.

A {
  color: blue;
  text-decoration: none;
  border-bottom: 1px solid red;
}
A.dotted {
  border-bottom-style: dotted;
}
A.dashed {
  border-bottom-style: dashed;
}

С помощью line-height со значением меньше единицы можно подтянуть бордер ближе к базовой линии:

A {
   display: inline-block;
   vertical-align: baseline;
   line-height: .95;
}

Метод с уменьшенным line-height годится только для ссылкок из одного слова, длинные разрывают поток и ломают подчёркивание:

Если разные стили линии не нужны, можно перекрасить стандартную underline с помощью вложенного элемента:

A {
  color: red;
}
A > SPAN {
  color: blue;
}

Такое подчёркивание, если присмотреться, перекрывает нижние выносные элементы букв:

Сергей Чикуёнок изобрёл подчёркивания ЦСС-градиентами:

A {
  color: blue;
  text-decoration: none;
  background: linear-gradient(left, red, red 100%);
  background-position: 0 95%;
  background-size: 10px 1px;
  background-repeat: repeat-x;
}
A.dashed {
  background: linear-gradient(left, red, red 60%, transparent 60%);
  background-size: 10px 1px;
  background-position: 0 95%;
  background-repeat: repeat-x;
}
A.dotted {
  background: linear-gradient(left, red, red 50%, transparent 50%);
  background-size: 2px 1px;
  background-position: 0 95%;
  background-repeat: repeat-x;
}

Его способ не работает в старых браузерах и достаточно неудобен на практике.

В будущем, когда все браузеры узнают свойства text-decoration-line, text-decoration-style и text-decoration-color из черновика ЦСС3, ваша задача решится элементарно:

A {
  color: blue;
  text-decoration-line: underline;
  text-decoration-style: solid;
  text-decoration-color: red;
}

Пример, демонстрирующий новые свойства, работает в Файрфоксе: