First let's consider why it is useful to have strings that are immutable. Consider the following sketch:
void Safe(string s)
{
if (!SecurityCheck(s)) { throw new SecurityException(); }
Dangerous(s);
}
Method Safe checks to see whether string s is "safe". Perhaps by "safe" we mean "the user is permitted to access this database table", or "the string contains no HTML that could be used in a cross-site scripting attack", or whatever. Only if the string is safe is it passed to a method that does something dangerous with it.
If strings were mutable then a clever attacker could pass a "safe" string and then after the security check, mutate the string to a "dangerous" string. Getting the timing right might be tricky, but of course attackers get to try multiple times, and they only have to succeed once.
This illustrates the first value of immutable data: facts deduced in the past about the data remain true in the future. If you have an immutable queue and you ask how many elements are in it, the answer you got five thousand nanoseconds ago is still correct. This enables you to make computations with confidence.
The second great value of immutable data is that it enables persistence. By persistence I don't mean ability to serialize to disk (though that is handy) but rather ability to re-use a portion of a data structure when building a larger data structure. If you have a large immutable tree and you would like it to be a sub-tree of a larger tree, no problem. You know that it's not going to change, so you can safely share the data. But if you have, say, a mutable queue and you'd like to use its contents in another data structure, you're going to have to make a copy.
That's just a brief sketch; see my series of articles on immutable data structures for more details:
http://blogs.msdn.com/b/ericlippert/archive/tags/immutability/