I know innerHTML is supposedly evil, but I think it's the simplest way to change link text. For example:
<a id="mylink" href="">click me</a>
In JS you can change the text with:
document.getElementById("mylink").innerHTML = new_text;
And in Prototype/jQuery:
$("mylink").innerHTML = new_text;
works fine. Otherwise you have to replace all of the child nodes first and then add a text node. Why bother?
How about
document.getElementById('mylink').firstChild.nodeValue = new_text;
This won't suffer from the problems described by PEZ.
Regarding Triptych's comment and bobince's reply, here's another solution:
var oldLink = document.getElementById('mylink'),
newLink = oldLink.cloneNode(false);
newLink.appendChild(document.createTextNode(new_text));
oldLink.parentNode.replaceChild(newLink, oldLink);