I'm wondering what a permutation matrix physically means. My initial thought is that it represents a reflection over some hyperplane. I'm guessing this because multiplying a basis by the same permutation matrix twice will give the original basis back. In addition, the orthogonality of a permutation matrix also makes me think that it could be a reflection (because length and angles have to be conserved).
Is this line of reasoning correct?
Yep --- it's a reflection ... at least the most basic ones are. If you permute $e_1$ and $e_2$ in $xyz$-space, the $x = y$ plane remains fixed, for instance, and this generalizes to higher dimensions as well --- a plane defined by orthogonality to the vector $e_i - e_j$ is left fixed by swapping $e_i$ and $e_j$.
When you permute $e_1, e_2, e_3$ anti-cyclically in 3-space, i.e., with the matrix $$ \pmatrix{ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 } $$ you've actually got a rotation, because the lines $x = y = z$ remains fixed.
In general, permutation matrices for even permutations are a product of a rotation and some even number of reflections; permutations with odd signature correspond to a product of rotations and an even number of reflections. As an example, consider $$ \pmatrix{ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 } $$ which is the product of two reflections, one through the $x = y, z, w$ hyperplane, and one through the $x, y, z = w$ hyperplane.