Now, let's look at the right side. m is mass, measured in kg. c^2 is the speed of light, measured in m/s. Thus mc^2 is kg * m^2 / s^2, which matches the units of E!
Notice that this dimensional analysis doesn't tell you ANYTHING about constants. You couldn't disprove E = 1/2 mc^2, or E = pi * mc^2, or E = SQRT(2) * mc^2, since 1/2, pi, and SQRT(2) are dimensionless constants. However, you could easily see that if you knew that E = m * c^k, where you didn't know the constant k, that the ONLY way for the units to match up would be to let k=2. The left side still has units of kg * m^2 / s^2. The right side has units of kg * m^k / s^k.