Permutations of $n^2$ elements can best be described by elements of the symmetric group of order $n^2$, written $S_{n^2}$. You are asking now how these permutations act on matrices. We could also ask more generally how these permutations act on elements of any vectorspace (matrices are, after all, also elements of the vector space $\mathbb{R}^{n^2}$).
It turns out that there is a whole theory behind this, called representation theory. A representation is a function $\rho$ (more precisely a group homomorphism) from a group $G$ to the invertible linear operators over a vector space $V$, i.e.: $\rho: G \rightarrow \operatorname{GL}(V)$. The objects in $\operatorname{GL}(V)$ can be described (in the finite dimensional case) as matrices. So $\rho$ associates a matrix to every group element.
In your case the group is $S_{n^2}$ and we wish to act with it on the vector space of $n \times n$ matrices, this corresponds to a representation $\rho: S_{n^2} \rightarrow \operatorname{GL}(\mathbb{R}^{n^2})$. If we let $\sigma \in S_{n^2}$ be a permutation we would expect something like this to happen:
$$
\rho(\sigma) \begin{pmatrix} a_{1} & a_{2} & \dots \\ a_{n+1} & a_{n+2} \dots \\ & \dots & \\ a_{(n-1)n} & a_{(n-1)n +1} & \dots \end{pmatrix}= \begin{pmatrix} a_{\sigma^{-1}(1)} & a_{\sigma^{-1}(1)} & \dots \\ a_{\sigma^{-1}(n+1)} & a_{\sigma^{-1}(n+2)} \dots \\ & \dots & \\ a_{\sigma^{-1}((n-1)n)} & a_{\sigma^{-1}((n-1)n +1)} & \dots \end{pmatrix}
$$
(We have to put $\sigma^{-1}$ there for $\rho$ to be a homomorphism, but this doesn‘t matter).
The matrix you were looking for is therefore exactly $\rho(\sigma)$, $\rho$ is in this case called the standart representation of $S_{n^2}$, and a well understood function. You can now go further and ask interesting questions like „Are there subspaces in the vector space $\mathbb{R}^{n^2}$, that are left invariant by all possible permutations?“, this is exactly what representation theory deals with.
I now this is a very theoretical answer that doesn’t tell you how the $\rho(\sigma)$ look like, but I hope that this could still show you how much fascinating theory there is behind your question:)
Edit:
The $\rho(\sigma)$ are exactly the permutation matrices linked to in the comment under your post. Notice though that we consider the matrices upon which is acted here as elements of a vector space and represent them therefore as vectors, so the permutation matrices/ the $\rho(\sigma)$ don’t act on the matrices by matrix multiplication but by „matrix vector multiplication“, i.e. you have to write the matrix that $\rho(\sigma)$ acts on as a column vector.
