EDIT: We may assume that the Picard number is at least two, as otherwise the cone is simply a ray generated by any effective curve. In particular, every effective curve is extremal.
I will also assume that "curve" means "effective curve".
(This edit was prompted by Damiano's comment that is now (sadly) deleted. It was a useful contribution.)
A curve on a surface is simultaneously a curve and a divisor and assuming the surface is smooth or at least $\mathbb Q$-factorial, then the curve, as a divisor, induces a linear functional on $1$-cycles. This works better if the surface is proper, so let's assume that.
So, if $C$ is such a curve, then the corresponding linear function on the space where $NE(S)$ lives is best represented by the hyperplane on which it vanishes and remembering which side is positive and which one is negative.
If $C$ is reducible, then it may have negative self-intersection, but it is not extremal. For an example, blow up two separate points on a smooth surface and take the sum of the exceptional divisors. My guess is that you meant irreducible, so let's assume that.
Now we have $3$ cases:
$C^2>0$. In this case $C$ is in the interior of the cone and it cannot be extremal, can't even be on the boundary (Use Riemann-Roch to prove this).
$C^2=0$. Since $C$ is irreducible, it follows that it is nef and hence a limit of ample classes, so it is effective, but as Damiano pointed out I have already assumed that. (It is left to the reader to rephrase this if $C$ is assumed to be nef instead of effective). In this case the hyperplane corresponding to $C$ as a linear functional is a supporting hyperplane of the cone, intersecting it at least in the ray generated by $C$. So $C$ is definitely on the boundary, but it may or may not be extremal depending on the surface. For example any curve of self-intersection $0$ on an abelian surface is extremal, but for instance a member of a fibration that also has reducible fibers is not extremal despite being irreducible. For the latter think of a K3 surface with an elliptic fibration that has some $(-2)$-curves contained in some fibers.
$C^2<0$. If $C$ is effective, then $C\cdot D>0$ for any irreducible curve $D\neq C$. This means that $C$ and all other irreducible curves lie on different sides of the hyperplane corresponding to $C$ as a linear functional, so the convex cone they generate must have $C$ generating an extremal ray.
Observe that we did not use the Cone Theorem. In fact one gets a different "cone theorem" this way:
Theorem
Let $S$ be a smooth projective surface $H$ an arbitrary ample divisor on $S$ and let
$$
Q^+=\{\sigma\in N_1(S) \vert \sigma^2 >0, H\cdot\sigma \geq 0 \}
$$
be the "positive component" of the interior of the quadric cone defined by the intersection pairing. Then
$$
\overline{NE}(S) = \overline{Q^+} + \sum_{C^2<0} \mathbb R_+[C]
$$
There is also one for $K3$'S, using the above notation:
Theorem
Let $S$ be a smooth algebraic K3 surface and assume that its Picard number is at least $3$. (If the Picard number is at most $2$, then there are not too many choices for a cone).
Then one of the following holds:
(i)
$$
\overline{NE}(S) = \overline{Q^+}, or
$$
(ii) $$
\overline{NE}(S) = \overline{\sum_{C\simeq \mathbb P^1, C^2<0} \mathbb R_+[C]}.
$$
The two cases are distinguished by the fact whether there exists a curve in $S$ with negative self-intersection. If the Picard number is at least $12$, then only (ii) is possible.
For proofs and more details, see The cone of curves of a K3 surface.
(There is also a newer version which is less detailed, but works in arbitrary characteristic. See here or here.)