Equivalence of skew-symmetric matrices

This is a counterexample. Let $O,I,J$ be the $2\times 2$ matrices $$\begin{pmatrix}0&0\\0&0\end{pmatrix},\,\,\begin{pmatrix}1&0\\0&1\end{pmatrix},\,\,\begin{pmatrix}0&1\\1&0\end{pmatrix},$$ respectively. Define the two $6\times6$ matrices $$A=\begin{pmatrix}O&I&I\\-I&O&I\\-I&-I&O\end{pmatrix},\,\,\,\,\, B=\begin{pmatrix}O&J&J\\-J&O&J\\-J&-J&O\end{pmatrix}.$$ We see that $B$ can be obtained by applying the permutation $(12)(34)(56)$ to the rows of $A$. On the other hand, there is no permutation $\sigma$ such that $A_{ij}=B_{\sigma(i)\sigma(j)}$. Unfortunately, I have no intuitive explanation why there is no such $\sigma$, but you can check this fact here (this is A) and here (this is B) --- there is no $\sigma$ sending the eigenvectors of $A$ to the eigenvectors of $B$.

Here is a simple explanation of why the matrices $A$ and $B$ in heptagon's answer are not permutation-similar. Suppose the contrary. Then their positive parts must be permuation-similar too, i.e. $$ A_+=\pmatrix{0&I&I\\ 0&0&I\\ 0&0&0} \ \sim\ B_+=\pmatrix{0&J&J\\ 0&0&J\\ 0&0&0} $$ via some permutation. This is impossible, because the directed graph represented by the adjacency matrix $A_+$ is comprised of the paths $1\to3\to5$, $1\to5$, $2\to4\to6$ and $2\to6$, so that a node can reach at most two other different nodes, while $B_+$ is comprised of the paths $1\to4\to5$, $1\to6$, $2\to3\to6$ and $2\to5$, so that each of node 1 and node 2 can reach three other different nodes.

Alternatively, if $A_+$ is permuataion similar to $B_+$, the directed graphs represented by these two adjacency matrices must be isomorphic. So, if we turn each edge to be an undirected one, the two undirected graphs must be isomorphic too. Yet this is impossible, because the undirected graph represented by $A_++A_+^T$ has two disjoint connected components $\{1,3,5\}$ and $\{2,4,6\}$, but $B_++B_+^T$ is a connected graph.