Why is the frequency complex
Why s is complex in the Laplace Transform: Note first that the Fourier Transform is a correlation (multiply and accumulate) of our time domain signal to every possible frequency. You could describe this correlation with sines and cosines (yuck!) or very compactly with exponentials (yes!). The Fourier Series Expansion is an excellent example of this in how it is typically first introduced, we step through every sine and cosine at the possible harmonic frequency locations and perform a correlation to see how much of our input signal in present at each frequency. Later we see the same equations in very compact form by describing our frequencies as single spinning phasors $$e^{j\omega t}$$ 
instead of carrying two phasors with the sines and cosines, such as: $$\frac{1}{2}e^{j\omega t} + \frac{1}{2}e^{-j\omega t}$$. 

See pictures at the bottom of this post to make this very clear, and look again at all the transforms (Fourier, Laplace, Z, etc) to see how in all cases this is a correlation of the form:

$$corr = \int f(t)g^*(t)dt$$

Which measures the linear relationship between two functions (* is complex conjugate).  For discrete systems the integral becomes a summation but again we see the correlation relationship.

Why is this important? So in Fourier we compute the correlation to all values of 

$$e^{j\omega t}$$

And see the content in our waveform for each frequency given by omega, and we have remapped our time domain waveform into the frequency domain, where certain mathematical challenges can be solved much more simply (or other reason related to observation or manipulation of the signal in frequency). 

Some waveforms will not converge in the correlation integral, and therefore do not have a Fourier Transform. However we can "pre-scale" those waveform by multiplying by a decaying exponential which will then allow the solution to converge:

$$e^{st} = e^{(\sigma + j \omega)t} = e^{\sigma t}e^{j \omega t}$$ 



The result is the Laplace Transform (in discrete systems the z-Transform), where again mapping our time domain waveform to the s-domain allows us to solve mathematical challenges much simpler (specifically Laplace converts differential equations to simple algebra--- yes!!!).  It also allows us to solve transient conditions such as step responses and the like.   And yes, you can picture the Laplace Transform as a surface showing the correlation of our input function x(t) to all possible spinning phasors (as in Fourier) as well as spinning phasors that grow or decay with time.  (Typically this surface is presented as just the poles and zeros showing where the correlation is maximum and zero since that completely describes the rest of the surface not shown.) 



Related to time and frequency and complex signals in general: A significant use of complex signals not yet mentioned is in communication systems. The modulation at any carrier for a linear system can be modeled directly at baseband (resulting in much simpler processing as we are no longer concerned with modeling every cycle of a high frequency sinusoidal carrier, but can just model the relatively lower rate of change in amplitude and phase directly of that carrier.)

That said, any waveform where the positive half of the spectrum is not the complex conjugate (not the same magnitude and opposite phase) when viewed at baseband as described above, can be described using complex signals; which covers nearly every modern communications waveform today (simple FM and AM modulations that are double sided are cases where this would not be necessary).

Euler's identity shows this quite well. Any real sinusoid has two complex signals given as a positive frequency and a negative frequency, obeying the rule that the frequencies must be conjugate symmetric. To create just one of these two frequencies (at baseband) we need to have a complex signal (often implemented with "I" and "Q" datapaths one representing the In-phase or real axis and the other representing the Quadrature or imaginary axis).  Each complex frequency is a phasor spinning in one direction versus time ($e^{j\omega t}$
).  The pictures below show this relationship in decomposing Euler's and also how a complex frequency is required if the positive half of the spectrum is not equal (complex conjugate) to the lower half:





The time domain signal is shown as a phasor (polar plot with vector representing instantenous time and angle, rotating with time). As those two phasors are equal and spinning in opposite directions (conjugate), a sinusoid that remains only on the Real axis wil result. Thus we see Euler's identity, the concept of positive and negative frequencies, and the reason we use complex frequencies.

Finally, here is a picture showing a case where the signal is modulated. In the picture we are centered at 0 (DC), but we could be equally centered at any carrier frequency with the same phase and amplitude deviation from the carrier versus time as depicted in the IQ (polar plot) diagram on the left. If our spectrum (on the right) does not have a complex conjugate relationship between the upper and lower half, we must use complex signals to describe that signal.