Say I have an elliptic curve $E: y^2 = x^3+4$ over $\mathbb{F}_{7}$. I want to find an $7$-torsion point in $\overline{\mathbb{F}}_7$ which is not in $\mathbb{F}_7$. How do I do that?
The $n$-torsion points are: $E[n] = \{P\in E(\overline{\mathbb{F}}_7)\mid nP = \infty\}$.
The $x$-coordinate $x_0$ of any nontrivial $7$-torsion point over $\overline{\mathbb{F}}_7$ is a zero of the $7$th division polynomial $\psi_7$ which is in your case equal to $5\cdot(x^3-2)^7$. Thus the $y$-coordinate $y_0$ of such a point satisfies $y_0^2=x_0^3+4=-1$. Thus any $7$-torsion point over $\overline{\mathbb{F}}_7$ is of the form $(x_0,y_0)$ where $x_0$ is a third root of $2$ and $y_0$ is a root of $-1$. Since the only cubes in $\mathbb{F}_7^*$ are $\pm 1$, the smallest subfield of $\overline{\mathbb{F}}_7$ containing a third root of $2$ is $\mathbb{F}_{7^3}$. Similarly, since $-1$ is not a square, the smallest subfield of $\overline{\mathbb{F}}_7$ containing a root of $-1$ is $\mathbb{F}_{7^2}$. Thus the smallest subfield of $\overline{\mathbb{F}}_7$ over which your curve has a nontrivial $7$-torsion point is $\mathbb{F}_{7^6}$, as predicted by Jyrki Lahtonen.