It's not just that the string is immutable, but also that while string is a reference type, a reference itself is not.  That is, you are passing the string by reference, but the reference itself is passed by value.
Thus, for reference types, you can modify the object that is referred to by the parameter (as long as it's modifiable), but you cannot modify what the argument refers to unless you pass it by reference.
So, when you try to change what the string variable refers to:
str = tmpStr;
It changes what str refers to locally, but does not affect what the original argument localString refers to.
Think of it this way, let's say that the argument localString refers to an object at location 1000:
localString 
+---------------+                      1000
|      1000     |   -----------------> +---------------+
+---------------+                      | Count: 1      |
                                       | Value: ""     |
                                       +---------------+
Then when we pass localString to the method, it creates a copy of the reference (as str) and updates the reference count...
localString 
+---------------+                      1000
|      1000     |   -----------------> +---------------+
+---------------+                      | Count: 2      |
                                       | Value: ""     |
str                                    +---------------+
+---------------+                        ^
|      1000     |   ---------------------+
+---------------+
Then, when you assign str to a new string, it modifies the reference str but not localString:
localString
+---------------+                      1000
|      1000     |   -----------------> +---------------+
+---------------+                      | Count: 1      |
                                       | Value: ""     |
str                                    +---------------+
+---------------+                          2500
|      2500     |   ---------------------> +---------------+
+---------------+                          | Count: 1      |
                                           | Value: ...    |
                                           +---------------+
So your modification of str only changed what str refers to, not the original refernce localString, if you want to change that, then you pass by reference, which means that str is a reference back to the original argument (much like a ptr to a ptr):
localString
+---------------+                      1000
|      2500     |  ------------------> +---------------+
+---------------+                      | Count: 2      |
        ^                              | Value: ""     |
str     |                              +---------------+
+---------------+       
|               |       
+---------------+                                                              
Now, when you change str it changes the refernce localString as well:
localString
+---------------+                      1000
|      1000     |  -----+              +---------------+
+---------------+       |              | Count: 0      |
        ^               |              | Value: ""     |
str     |               |              +---------------+
+---------------+       |                  2500
|               |       +----------------> +---------------+
+---------------+                          | Count: 1      |
                                           | Value: ...    |
                                           +---------------+
And then, of course, the original string (assuming nothing else refers to it as in this example) can be garbage collected...
So, if you really want to modify the string parameter, pass it by ref or out, or you can return the new mutated version, or store in an instance member (though pass-by-instance-member is a higher order of coupling and can cause other issues...).