Although the proof of Euler's formula through power series is sufficient, I personally like the proof that my calculus textbook uses, with good old differential equations. I'll try to explain it here, in all its creamy HTML goodness.

Suppose you "pull an equation out of thin air":

y = cos x + i sin x (also known as cis x)

where i = √-1. Note that this equation basically means that if x is an angle in radians, than y is the position of that angle's point on a unit circle in the complex plane. That's not important, though. We take the derivative of each side with respect to x:

d/dx(y) = d/dx(cos x + i sin x)
dy/dx = -sin x + i cos x
dy/dx = i(i sin x + cos x)
dy/dx = i(cos x + i sin x)

Therefore, because of the first equation,

dy/dx = iy

Freaky already. This is where the differential equation comes in. Manipulating things around:

1/y dy = i dx
1/y dy = ∫i dx
ln |y| = ix + C
|y| = Ceix
y = ±Ceix

And therefore by substitution:

±Ceix = cos x + i sin x

Setting x to 0 to find out C:

±Ce0i = cos 0 + i sin 0
±C = 1
C = 1

Since C has to equal 1 (and the negative C is unneccesary, as it's false for x = 0), we can forget about it.

eix = cos x + i sin x

Fun stuff. Substituting π for x gives the equation that everyone's talking about:

eiπ = -1

or, as most prefer to express it:

eiπ + 1 = 0.