I am quite sure this is true, that for a $n\times n$ nondegenerate permutation matrix, $$\exists k\in \mathbb N: {\bf P}^k={\bf I}$$
But what is the easiest / most elegant way to prove it?
Edit: changed the set for $k$ to $\mathbb N$ from $\{0,1,\cdots,n\}$
The group Donald presented in the comments has a generating element that can be represented with the permutation matrix:
$${\bf M}_{{G_S}_5}=\left[\begin{array}{cc|ccc}0&1&0&0&0\\1&0&0&0&0\\\hline 0&0&0&1&0\\0&0&0&0&1\\0&0&1&0&0\end{array}\right]$$
Where the lines show the diagonal block structure separating (45) (upper left) from (123) (down right) and we can verify $6$ is the lowest exponent equalling unity: $({\bf M}_{{G_S}_5})^6 = {\bf I}$
The $n \times n$ permutation matrices form a finite group (with matrix multiplication as operation) of order $n!$, and it is a well-known result that all elements in a finite group have finite order (specifically, their order divides the order of the group). The identity matrix is of course the identity element in this group.
Specifically, because the order of the group is finite, the sequence: $$ (a^1,a^2,a^3,\dotsc) $$ must repeat for all group elements $a$, with period at most the order of the group (i.e. $n!$ in this case). Hence there are $m,k \in \mathbb N$ such that $m < k$ and $a^m = a^k$. But then $a^{k-m}$ is the identity.