@JTT,
"they always seem to say that":
On every occaision they look like they are saying that, though they may not actually be, as "seem" allows for error, illusion, etc
"it seems they always say that":
I get the impression, though it may not be reliable, that they say that every time.
So it's about what the "seem" applies to, the saying or the always.