The Frobenius eigenspace of $-1$ is, by definition, the kernel of the map $π+1$. Typically, this is further restricted to some torsion group $E[ℓ]$, so we are really talking about $E[ℓ] ∩ E[π+1]$, i.e., those points of $E[ℓ]$ such that $π(P)=-P$.
If the curve is expressed in Weierstrass form $y^2=f(x)$ (or Montgomery, or similar), letting $P=(x,y)$ we have $-P=(x,-y)$. Thus the Frobenius eigenspace is made by those points $(x,y)$ such that $x^p=x$ and $y^p=-y$. A little theory shows that this is the set of rational points of the twist of $E/𝔽_p$.
So, the obvious way to sample the points is to
- Choose a random $x\in 𝔽_p$;
- Check that $f(x)$ is not a square, i.e., that $y=\sqrt{f(x)}$ is not in $𝔽_p$, i.e., that $y^p=\sqrt{f(x)}f(x)^{(p-1)/2}=-\sqrt{f(x)}=-y$;¹
- See $(x,y)$ as a point in $E/𝔽_{p^2}$, multiply by an appropriate cofactor to obtain a point in $E[ℓ]$.
¹To see why this works, note that $f(x)$ is not a square in $𝔽_p$, thus its Legendre symbol is $-1$. By the way, saying $x$ is in $𝔽_p$ and $y$ is not is equivalent to saying that $x$ is the abscissa of a rational point on the twist.
If $\#E(𝔽_p)=p+1-t$, where $t$ is the trace of $π$, then the twist has order $p+1+t$, thus the "appropriate cofactor" above is $(p+1+t)/ℓ$. Note that $E[π+1]∩E[π-1]=E[2]$ (because $1=-1\mod 2$), thus for $ℓ=2$ the two ℓ-restricted eigenspaces are indistinguishable, and you would get a random point of order $2$; however for any other prime $ℓ$ there are two distinct eigenspaces, and step 3. will stay in the twist.
Steps 1. and 2. above can be replaced by Elligator 2, which samples simultaneously in both the eigenspace of $+1$ and that of $-1$. The original Elligator 2 was explained as a map to $E[π-1]$, but the generalization to a map to $E[π-1]×E[π+1]$ is easy and has been hinted at in several papers. For an explicit description, see Section 3, and Algorithm 3 in particular, here: https://eprint.iacr.org/2019/837.
All this can be generalized to arbitrary eigenvalues $λ$, not just $±1$. The multiplicative order of $λ$ in $ℤ/ℓℤ$ determines the degree of the extension of $𝔽_p$ where the points $E[π-λ]$ are defined.