What does the order of a permutation actually mean? I accept the fact that it is the l.c.m. of the lengths of the cycles in its cycle decomposition, but I don't really have an intuition for what the order of a permutation actually means.
I have an intuition for the order of a set of permutations like $S_n$ -- namely, it is the cardinality of the set. However, this intuition isn't translating well to thinking about the order of a specific permutation.
On
The order of an element $x$ in a group $G$ is the smallest positive integer $n$ such that $x^n = e$.
Let's take the group $S_5$ and look at the permutation $\sigma = \begin{pmatrix}1&2&3&4&5\\3&1&2&5&4\end{pmatrix}$.
Now, apply this permutation repeatedly to $(1,2,3,4,5)$:
$\sigma^1$: $(3,1,2,5,4)$
$\sigma^2$: $(2,3,1,4,5)$
$\sigma^3$: $(1,2,3,5,4)$
$\sigma^4$: $(3,1,2,4,5)$
$\sigma^5$: $(2,3,1,5,4)$
$\sigma^6$: $(1,2,3,4,5)$
So, we need to apply this permutation $6$ times to get back what we started with. Hence, the order of this permutation in $S_5$ is $6$. Notice that after an even number of applications of $\sigma$, the $4,5$ are back in the right order. Also, after any multiple of $3$ applications of $\sigma$, the $1,2,3$ are back in the right order. Thus, we need $\text{lcm}(2,3) = 6$ applications of $\sigma$ to get all the numbers in the right order.
$S_n$ is a group with composition of functions. And as such, given $\sigma \in S_n$, we can consider the subgroup of $S_n$ generated by $\sigma$, that is, $\langle \sigma \rangle = \{\mathrm{id}, \sigma, \sigma^2, \ldots, \sigma^{k-1} \}\leq S_n$ (meaning $\sigma^k = \mathrm{id}$). As in any group, the order of the element is the cardinality of the subgroup generated by the element. Since $|\langle \sigma \rangle| = k$, the order of $\sigma$ is $k$, in the example above.