I am not sure if any of the answers actually cared to explain why [math]x \sqcup y > y \sqcup x[/math] is a good rule, so I'll try to explain it. Let's call this relation [math]R(x,y)[/math]

There are many possible permutations, and some of them are optimal (observe that there can be more than one good solution).

The claim is that :
1. in an optimal permuation [math]p_1,...,p_n[/math] for every two consecutive elements [math]p_i, p_{i+1}[/math] it can not be that [math]R(p_{i+1},p_i)[/math] (but it can be that [math]R(p_i,p_{i+1})[/math] does not hold neither)
2. the relation R is transitive, irreflexive and antysymetric, so it forms a strict order.
3. (=1+2) for any two indices [math]i<j[/math], it can not be that [math]R(p_{j},p_{i})[/math].
4. Swapping two consecutive elements such that neither [math]R(p_i,p_{i+1})[/math] nor [math]R(p_{i+1},p_{i})[/math] does not change the concatenated string.
6. (=2+4) one of optimal solutions can be obtained by sorting the input sequence using [math]R[/math] to compare elements. Moreover all optimal solutions look the same after concatenation (it should not be surprising).

Let us start with definition of "another" retlation
[math]S(x,y) \iff x \sqcup x \sqcup ... \sqcup x > y \sqcup y \sqcup ... \sqcup y [/math].
As others already mentioned [math]S(x,y) \iff R(x,y)[/math], and here is the proof: when comparing x and y as in the definition of R, character by character from left to right you either find the difference before x and y end, in which case the comparison in S has the same result, or you will continue the comparison using characters from the other string. But, in the latter case, the previously compared characters were equal, which means that the beginning of the other string is actually equal to the prefix of the first string. The longer the comparison goes the more sure we are that the longer string is actually a prefix of probably multiple copies of the shorter one. A picture would be in place here. I know this is not a strict proof, so edits are welcomed;)

Proof for 1. If [math]R(p_{i+1},p_i)[/math] then swapping [math]p_{i+1}[/math] and [math]p_{i}[/math] will lead to a better string after concatenation.
Proof for 2. Transitivity is the most difficult to show. At least for R because inequalities involve two variables on both sides. But for S it is quite obvious!
Proof for 3. Actually it does not follow directly from 1 and 2. But it could be shown using S instead of R. First one have to observe that if neither S(x,y) nor S(y,x) than x* = y*
Proof for 4. This is again is not so obvious unless the equivalence is shown.
Proof for 6. Sort algorithm given a strict order returns one of possible permutations which does not violate this strict order. In such permutation elements which are not comparable are clumped together in groups, and each element of each group is in relation with an element of each other group. This can be said about any optimal solution as well. It suffices to show that any optimal solution can be achieved by swapping incomparable elements.