As Pinu7 said, c^2 has units of length^2/time^2, and you can see that you'd need a constant of this type in an equation relating mass to energy because energy has units of mass*length^2/time^2.
One way of thinking about it is in terms of reactions that convert rest mass into kinetic energy or vice versa--for example, when matter and antimatter particles collide they convert into a pair of photons, and energy is conserved in spite of the fact that the kinetic energy of the photons is much greater than the kinetic energy of the original particles, as long as you include the particles' rest mass as a type of energy which was converted to kinetic energy for the photons (which have zero rest mass).
Another way of thinking about it is that if you use something like a scale to measure the mass of a bound system (like an atom, or a bunch of particles in a box, or a solid object), all forms of energy in the system combine to give the reading you get--thus for example a brick will weigh slightly more if you heat it up, because the heat increases the average kinetic energy of the particles that compose it, and likewise an electron and proton weigh slightly less when bound into a hydrogen atom than they do when weighed individually, because when bound into an atom their potential energy is lower.