I know you're mostly looking for an intuitive explanation, but I think it's important to at least get a feel for the mathematical truth of this equation first. So I'll give a (much) shortened derivation of it first and get to the intuition part later.
The mathematics
Einstein's theory of special relativity tells us the energy $E$ of a particle is given by
$$E^2 = |\vec{p}|^2c^2+m^2c^4,$$
which can be derived from the free-particle Lagrangian in Minkowski space (a flat version of spacetime) and the definition of canonical (four-)momentum $p=(p^0,\vec{p})$. Working out this definition for the free-particle case gives you the components of the four-momentum:
$$p^0 = \frac{mc}{\sqrt{1-\frac{v^2}{c^2}}} \hspace{2cm} (*)$$
$$\vec{p} = \frac{m\vec{v}}{\sqrt{1-\frac{v^2}{c^2}}} \hspace{2cm} (**)$$
From this you can find an expression for the relativistic energy by considering the time component $p^0$ in the limit $v\ll c$:
$$p^0 = \frac{mc}{\sqrt{1-\frac{v^2}{c^2}}} \approx mc\left(1+\frac{1}{2}\frac{v^2}{c^2}\right)$$
so
$$cp^0 \approx mc^2+\frac{mv^2}{2}\hspace{2cm}(1)$$
The second term looks familiar. Indeed, it's our old friend the kinetic energy $T$. Since we're talking about a free particle, there's no potential energy. So what's this $mc^2$ term doing there? And how should we interpret $cp^0$? Well, rewriting equation $(1)$ gives us
$$T = cp^0 - mc^2.$$
From this, it should seem obvious that $cp^0$ is the total energy $E$ of the free particle and $mc^2$, which depends only on an intrinsic property of the particle (its mass), is some sort of rest energy the particle cannot get rid of. The only way for the particle to change that part of its energy is to somehow changes its mass, which is hard to do, even with the strictest of diets.
Of course particles don't go on diets (excuse that humorous outburst of mine just a moment ago) but they can change their mass if they're prepared to give up on their entire identity. But more on that in the intuition part below. Let's first get our focus back on the mathematics.
Remember that equation $(1)$ only holds for small $v$. Going back to general $v$, we can now use $p^0 = E/c$ to calculate the length of the four-momentum. Recall that the length of a vector $\vec{a}$ is the square root of the inner product of $\vec{a}$ with itself, i.e. in 3D Euclidian space
$$|\vec{a}| = \sqrt{\vec{a}\cdot\vec{a}}$$
or
$$|\vec{a}|^2 = \vec{a}\cdot\vec{a} = \sum_{i=1}^3{a_i^2}$$
In Minkowski space, things are slightly different. The technical details aren't that important, the relevant consequence for us is this: the basic form of the previous formula is the same, but it is slightly adjusted$^1$:
$$|a|^2 = \sum_{\alpha=0}^3{g_{\alpha\alpha}a_{\alpha}^2}.$$
Note that I use a simple letter to denote a four-vector and a letter with an arrow over it for a 3D vector. Furthermore, I've used the convention that Greek letters ($\alpha$) serve as indices for components of four-vectors, in contrast to the Latin letters ($i$) for three-vector components.
Note also that there is some factor $g_{\alpha\alpha}$ appearing in the new expression for vector lengths. This factor has two indices and thus constitutes a rank 2 tensor (or matrix) called the metric tensor. This object sort of draws out what you could call the geometry of the space in which we're working. It tells us how to measure lengths. In particular, this metric tensor consists only of diagonal elements $g_{\alpha\alpha}$ which are either $+1$ or $-1$. It's a matter of convention which elements are positive and which negative, we'll choose $g_{00} = +1$ and the rest $-1$.
All this to show you that the length of a four-vector in Minkowski space is calculated as
$$|a|^2 = a_{0}^2 - \sum_{i=1}^3{a_i^2}.$$
For our momentum vector $p = (p^0,\vec{p}) = (E/c,\vec{p})$ this becomes
$$\begin{align}
|p|^2 &= E^2/c^2 - \sum_{i=1}^3{p_i^2} \\
&= E^2/c^2 - |\vec{p}|^2
\end{align}$$
Keeping in mind that $E = cp^0$ we now use $(*)$ and $(**)$ to find
$$\begin{align}
|p|^2 &= E^2/c^2 - |\vec{p}|^2 \\
&= \frac{m^2c^2}{1-\frac{v^2}{c^2}} - \frac{m^2v^2}{1-\frac{v^2}{c^2}} \\
&= m^2c^2\left(\frac{1}{1-\frac{v^2}{c^2}} - \frac{v^2/c^2}{1-\frac{v^2}{c^2}}\right) \\
&= m^2c^2
\end{align}$$
Combining the first and last lines we get
$$E^2/c^2 - |\vec{p}|^2 = m^2c^2$$
which can be rewritten into the equation we were searching for
$$E^2 = |\vec{p}|^2c^2 + m^2c^4$$
or if the particle is at rest ($\vec{p} = \vec{0}$):
$$E = mc^2.$$
The intuition
Now, that's all grand, but what does it mean? Well, it means mass and energy are not two separate quantities. In fact, they are the same up to a constant factor of $c^2$ (let's consider particles at rest). So what happens in fission reactors? Simply put, an atom's core collides with a neutron, briefly exciting the core into a higher isotope. This excited state is unstable and the core splits into two smaller, (more) stable cores. These two cores have a lower combined mass than the total mass of the original excited core. The difference in mass is released as energy in accordance with the formula we have just derived.
Then why isn't this possible with iron for example? That's a very good question. To answer it, let's think about what the core of an atom actually is. It consists of protons and neutrons, held together by the strong nuclear force. Aha! Wait a minute! Protons and neutrons are not point particles. They have a finite volume. So the more there are in a core, the bigger the core will be. But protons are also charged particles and they repel each other through the electrostatic interaction!
Now, the strong nuclear force is a short-distance attractive force, the electrostatic interaction is long-distance and repelling for equal charges. So the larger the core, the closer the protons at the edge of the core will get to feeling equally strong repelling and attracting forces. That should give you an intuition as to why some cores are unstable (it's also why there is an end to the periodic table, higher cores are too unstable to exist in nature).
This puts a lower bound on the cores that are 'fissionable'. There are models for this, but the important thing is that iron is definitely below the lower bound. In fact, it is the most stable core in existence. To get it to split, you would need to put a whole lot more energy into it than you would get out.
$^1$ I'm neglecting some notational details, which are in fact important but not in this context. Here I stayed as close to the form of the better-known equation for the length of a 3D vector to avoid having to discuss covariance and contravariance. So some of my notation is strictly speaking incorrect and I'm slightly inconsistent by switching between denoting the components of the four-vector $p$ with an upper index and those of the four-vector $a$ with a lower index. But the notational inaccuracies have no further consequences and the discussion itself is not affected.