$E=mc^2$ is the famous equation that states the equivalence of mass and energy, with a conversion factor in units of $\text{m}^2/\text{s}^2$.
But in my naive mind, the conversion factor of mass and energy would be in units of $\text{J}/\text{kg}$.
How can I make the mental leap into seeing these two seemingly entirely unrelated units as the same thing?
The answer to your question lies in simple dimensional analysis.
Joules are the units of energy, so also the units of work. Work, as we all know, satisfies the relationship $$W=\vec F \cdot \vec s$$ Meanwhile, $$\vec F= m \vec a$$ Substituting in this relationship gives us $$W=m\vec a \cdot\vec s$$
Now, let's look at the units of this equation: $$[\text{J}]=[\text{kg}][\text{m}]^2[\text{s}]^{-2}$$
Clearly, then, $$ [\text{J}][\text{kg}]^{-1}=[\text{m}]^2[\text{s}]^{-2}$$ and both units are equivalent: $c^2=(299792458)^2\ \text{J}\ \text{kg}^{-1}$
The reason why we can invoke these unrelated equations to analyze the dimensions of the quantities involved is because every expression in physics must be consistent (dimensionally), so in terms of units they all express the same things, and we get to pick whichever is simplest to solve our problem.
The kinetic energy is given by $E_c=\frac12mv^2$, as the factor $1/2$ is dimensionless, you can see that $\mathrm{[m^2.s^{-2}]=[J.kg^{-1}]}$. Dimension analysis remains correct if the velocity $v$ takes the value $c$, because $c$ is also a velocity.
