Given three permutations of $\{1,2,\dots,n^3+1\}$, prove two of them have a common subsequence of length $n+1$.

I think you want to imitate the proof of the Erdos-Szekeres theorem, not apply it directly. Label each $1\le j\le m$ with the triple $(a,b,c)$ where $a$ is the length of the longest common subsequence of $\sigma_1$ and $\sigma_2$ that ends in $j,$ $b$ is the longest common subsequence of $\sigma_1$ and $\sigma_3$ that ends in $j,$ and $c$ is the longest common subsequence of $\sigma_2$ and $\sigma_3$ that ends in $j.$

I claim that no two elements get the same label, for suppose $1\le j,k \le m,$ with $j\ne k$ and that both $j$ and $k$ get the same label. If $j$ precedes $k$ in both $\sigma_1$ and $\sigma_2$ then $k$ has a larger $a-$label than $j$, since we can append $k$ to the largest common subsequence ending in $j$. Similarly, $k$ cannot precede $j$ in both $\sigma_1$ and $\sigma_2$ so we can assume $j$ precedes $k$ in $\sigma_1$ and $k$ precedes $j$ in $\sigma_2$. Then $j$ and $k$ must come in the same order in $\sigma_3$ as either $\sigma_1$ or $\sigma_2$ so that they have different $b-$labels or different $c-$labels.

If the longest commons subsequence is of length $n$ or less, then there are at most $n^3$ different labels, but we have $n^3+1$ different labels, contradiction.

EDIT It's just occurred to me that there are many proof of the Erdos-Szekeres theorem known. I'm referring to the one here