Einstein found this result in a 1905 paper, titled "Does the inertia of a body depend upon its energy content?" This paper is very short and readable, and is available online. A summary of the argument is as follows. Define a frame of reference A, and let an object O, initially at rest in this frame, emit two flashes of light in opposite directions. Now define another frame of reference B, in motion relative to A along the same axis as the one along which the light was emitted. Then in order to preserve conservation of energy in both frames, we are forced to attribute a different inertial mass to O before and after it emits the light. The interpretation is that mass and energy are equivalent. By giving up a quantity of energy E, the object has reduced its mass by an amount E/c2.
Although Einstein's original derivation happens to involve the speed of light, E=mc2 can be derived without talking about light at all. One can derive the Lorentz transformations using a set of postulates that don't say anything about light (see, e.g., Rindler 1979). The constant c is then interpreted simply as the maximum speed of causality, not necessarily the speed of light. Constructing the mass-energy four-vector of a particle, we find that its norm E2-p2c2 is frame-invariant, and can be interpreted as m2c4, where m is the particle's rest mass. In the case where the particle is at rest, p=0, and we recover E=mc2.