CSS transition not working with underline

Updated for 2021:

The support for text-decoration-color has come a long way, and common browser support requirements have loosened making it a viable option for most new projects. If you are only seeking a color transition, and can do without IE support, see this answer below.

Original answer:

You cannot change the color of the text-decoration independent of the color. However, you can achieve a similar effect with pseudo elements:

.un {
  display: inline-block;
}

.un::after {
  content: '';
  width: 0px;
  height: 1px;
  display: block;
  background: black;
  transition: 300ms;
}

.un:hover::after {
  width: 100%;
}

<span class="un">Underlined Text - Or to be underlined</span>

That is the most customizable way to do it, you can get all sorts of transitions. (Try playing around with the margins/alignment. You can make some awesome effects without adding to your HTML)
But if you just want a simple underline, use a border:

.un {
  transition: 300ms;
  border-bottom: 1px solid transparent;
}

.un:hover {
  border-color: black;
}

<span class="un"> Underlined Text - Or to be underlined </span>