Gauss's first proof goes more or less like this. Let $p(z)$ be a polynomial of degree $n$ and complex coefficients. Write $p(x+iy) = a(x,y) + ib(x,y)$, where $a,b$ have real coefficients. The crucial observation is that the branches of $a=0$ and $b=0$ as real curves interlace at infinity (as can be seen from the degree $n$ terms). Also, real algebraic plane curves don't just stop somewhere in the affine plane, so a branch of $a=0$ must be connected to another branch of $a=0$. Now, in between them, there is a branch of $b=0$ which connects to another branch of $b=0$. If the connections alternate, they have to meet and we get a common zero of $a$ and $b$, which gives a complex zero of $p$. If they don't alternate, find a branch of $a=0$ in between the two connecting branches of $b=0$ and repeat.
I think this proof really needs the Jordan curve theorem to be fully justified, which is a bit of an anachronism.
