The paper introducing the application of endomorphisms in arbitrary curves to cryptography was Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, ‘Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms’, in Joe Kilian, ed., Proceedings of Advances in Cryptology—CRYPTO 2001, Springer LNCS 2139, pp. 190–200, after the initial idea of Neil Koblitz, ‘CM-Curves with Good Cryptographic Properties’, in Joan Feigenbaum, ed., Proceedings of Advances in Cryptology—CRYPTO 1991, Springer LNCS 576, 1991, pp. 279–287 (after whom the class of curves with efficient endomorphisms is named) to exploit the Frobenius endomorphism when it has trace 1 in binary curves.
The basic idea is that sometimes there is a scalar $\lambda$ such that computing $[\lambda]P$ given the $(x, y)$ coordinates of a point $P$ on the curve can be computed much more efficiently than by the standard double-and-add algorithm on the binary expansion of $\lambda$.
Here's a class of examples. Let $p \equiv 1 \pmod 3$ be a prime, and let $$E/\mathbb F_p\colon y^2 = x^3 + b$$ be an elliptic curve over the finite field $\mathbb F_p$ of $p$ elements. Suppose $\beta \in \mathbb F_p$ is an element of order 3, so that $\beta^3 \equiv 1 \pmod p$. The map $f\colon (x, y) \mapsto (\beta x, y)$ (and $f\colon \mathcal O \mapsto \mathcal O)$ is an endomorphism—if $(x, y)$ is on the curve so that $y^2 = x^3 + b$, then $$y^2 = x^3 + b = 1\cdot x^3 + b = \beta^3 x^3 + b = (\beta x)^3 + b$$ so that $(\beta x, y)$ is also on the curve. (Verifying $f(A + B) = f(A) + f(B)$ is left as an exercise for the reader.) Of course, $\beta = 1$ satisfies $\beta^3 \equiv 1 \pmod p$, but the map is interesting only if $\beta$ is a nontrivial cube root of unity, a root of $\beta^2 + \beta + 1$, which exists iff $3 \mid \phi(p) = p - 1$ so that $p \equiv 1 \pmod 3$. It turns out that if $B \in E(\mathbb F_p)$ is an element of prime order $n$, and $\lambda$ is a root of $\lambda^2 + \lambda + 1$ modulo $n$, then for any scalar $k$, $f([k]B) = [\lambda \cdot k]B$. (Obviously, this requires that $n \equiv 1 \pmod 3$ too.)
In brief, in the subgroup generated by $B$, computing $(x, y) \mapsto (\beta x, y)$, which costs only a single multiplication in the coordinate field $\mathbb F_p$, is a much cheaper way to compute $P \mapsto [\lambda]P$ than the standard double-and-add algorithm on the binary expansion of $\lambda$, which costs $H(\lambda) - 1$ additions and $\lfloor\log_2 \lambda\rfloor$ doublings, where $H(\lambda)$ is the Hamming weight of $\lambda$.
To take advantage of this, for any scalar $k$, write $k \equiv k_1 + k_2 \lambda \pmod n$; then to compute $[k]P$, you can reduce it to
\begin{align*}
[k]P &= [k_1 + k_2 \lambda]P \\
&= [k_1]P + [k_2]([\lambda]P) \\
&= [k_1]P + [k_2]f(P).
\end{align*}
The GLV paper goes into a little more detail about how to turn this into a complete scalar multiplication algorithm. Unfortunately, the recursive decomposition of $k$ itself has costs, so the net improvement is only a modest 50% or so.
To generate a new prime Koblitz curve, or GLV curve, exploiting this particular endomorphism, lay out candidate primes $p_0, p_1, p_2 \ldots$ and curve parameters $b_0, b_1, b_2, \dots$ in some order of preference (say, primes nearest a power of two below it, and smaller parameters), and pick the first $p_i$ and $b_i$ such that
- $p_i$ is prime,
- $p_i \equiv 1 \pmod 3$,
- the number $\ell_i$ of $\mathbb F_{p_i}$-rational points on the curve $E/\mathbb F_{p_i}\colon y^2 = x^3 + b_i$ is prime,
- $\ell_i \equiv 1 \pmod 3$, and
- all other security criteria of interest are satisfied.
Next, pick a generator $g$ of $\mathbb F_{p_i}$, and let $\beta = g^{(p_i - 1)/3} \bmod{p_i}$; and pick a generator $h$ of $\mathbb Z/\ell_i\mathbb Z$, and let $\lambda = h^{(\ell_i - 1)/3} \bmod{\ell_i}$. These are by construction cube roots of unity, since, e.g., $\beta^3 \equiv (g^{(p_i - 1)/3})^3 \equiv g^{p_i - 1} \equiv 1 \pmod{p_i}$, and they are nontrivial because if $g$ generates $\mathbb F_{p_i}$ then it must have order $\phi(p_i) = p_i - 1$ and so $g^{(p_i - 1)/3} \not\equiv 1 \pmod{p_i}$. Since there are two nontrivial cube roots of unity in each group, they may be mismatched like socks: you may have to use $\ell_i - \lambda - 1$ instead, or $p_i - \beta - 1$ instead, to make them match.
For binary Koblitz curves, see Koblitz's original paper. The endomorphism in this case, on the $\mathbb F_{2^m}$-rational points, is the Frobenius map $f\colon (x, y) \mapsto (x^{2^m}, y^{2^m})$, with which $[2^m]P$ can be computed by $f(P) - f^2(P)$. The trick is to find an appropriate extension field $\mathbb F_{2^m}$ over one of the four curve shapes $y^2 + x y = x^3 + a x^2 + b$ where $a, b \in \{0,1\}$.
