There is another O(n) solution. It has a better constant, but may or may not perform better in practice due to cache locality issues.
I call it the "two handed" algorithm, because you need "two hands" to do it. :-)
Basically, you pick up the characters in position 0 and position m, then you put down the character from position 0 into position m. Now holding only the character originally in position m, you pick up the character from position 2m and put down the new character for that position. When you reach a multiple of m that is past the end of the string, you wrap around to the beginning. Repeat until you are back at position 0.
If m and n were co-prime, you're already done. If not, then you need to repeat with positions 1, m+1, 2m+1, .., and then 2, m+2, 2m+2, .., and so on. You can stop at GCD(n,m), since this position will have been reached by the first loop starting at position 0.
Pseudocode:
num_cycles = GCD(n, m)
cycle_length = n / num_cycles
for cycle = 0 to num_cycles - 1
index = cycle
value = string[index]
do
index = (index + m) mod n
-- Note: The following can be implemented as a swap.
next_value = string[index]
string[index] = value
value = next_value
loop while index <> cycle
end for