To explain the above responses a little: this is called dimensional analysis.
If you think energy E depends on mass m and the speed of light c, then how must those things be combined? The most general way is like this:
[tex]E = km^\alpha c^\beta[/tex]
where [itex]\alpha[/itex] and [itex]\beta[/itex] are constants to be determined, and k is a dimensionless constant (a number without units).
Now, energy, in SI units, is in Joules, and 1 Joule is 1 kilogram (metre/second)^2. The dimensions of energy are therefore mass.(length/time)^2, often written: [itex][M][L]^2[T]^{-2}[/itex].
Similarly, the dimensions of m are: mass, or [itex][M][/itex]
The dimensions of c are: (length/time), or [itex][L][T]^{-1}[/itex]
Putting these dimensions into the general equation, we get:
[tex][M][L]^2[T]^{-2} = k([M]^\alpha)([L]^\beta [T]^{-\beta})[/tex]
We want to solve for alpha and beta. Matching the dimensions on the left and right hand sides gives:
[tex][M]: \alpha = 1[/tex]
[tex][L]: \beta = 2[/tex]
[tex][T]: -\beta = -2[/tex]
Therefore, our expression must be:
[tex]E = kmc^2[/tex]
This doesn't tell us what k is. k could be 1 or 17 or [itex]pi[/itex], or some other number. To find k, we need to derive the equation from physical arguments. If we do that, we find that k=1.
However, this argument is enough to show you that the speed of light must be squared.