I don't know how Euler came up with it, but here's a fairly intuitive way: think about circular motion. If something moves around a circle at constant speed, then its velocity vector is perpendicular to the vector from 0 to the moving thing. Once you have the idea (which isn't terribly difficult) that complex numbers live on a plane and multiplication by i is rotation through a right angle, this gives you the differential equation dx/dt = ix. Solving that is easy: x = exp(it). Since it's also easy (by definition of the trig functions) to see that x = cos t + i sin t, we're done.

Given the sort of thing Euler was good at, though, it seems just as likely that he looked at the power series for sin, cos, and exp, and said "aha!".