What type of energy does the $E$ in $E=mc^2$ represent?

The $m$ in $E=mc^2$ is called "the relativistic mass" and is part of the algebra of special relativity.

$$m=frac{m_0}{sqrt{1-frac{v^2}{c^2}}}=gamma m_0$$ $m_0$ = "rest mass"

Note the dependence on velocity, and note that velocity so this mass is variable, it is the inertial mass of an object , i.e. the resistance to becoming accelerated in classical terms. It is no longer used in particle physics because of this variability. What characterizes particles is the rest mass, or invariant mass. This, in the four vector algebra, is the length of the given four vector:

$$sqrt{Pcdot P}=sqrt{E^2-(pc)^2}=m_0c^2$$

The length of this 4-vector is the rest energy of the particle. The invariance is associated with the fact that the rest mass is the same in any inertial frame of reference.

It is the $m_0c^2$ that is the inherent available energy of a particle due to the mass. When the particle is at rest, i.e momentum is equal to zero, all the energy is in the rest mass as the formula shows. When a particle meets an antiparticle twice this mass-energy is available in the annihilation.

Also in nuclear physics , the rests mass of the nuclei shows if it is possible to fission or fusion into other nuclei.

In the last formula, the total energy of a particle minus the kinetic energy, give the invariant mass.The concept of potential energy does not enter when using four vector algebra.

(a) "Does this represent that if an object has mass, it inherently has energy associated with that mass[?]" Yes.

(b) "[I]s the energy in an object stored as mass unrelated to all the other forms of energy (potential, kinetic, etc), or is it related to them?" No. The mass of the object includes all the energies stored in the object, as measured in the frame in which the object's centre of mass is at rest. So, for example a sample of gas whose kinetic energy of random molecular motion amounts to 25 J will have a contribution to its mass of $(25 text J)/c^2$.

(c) "If I increased an object's potential energy by lifting it up, would its mass change?" You must remember that potential energy cannot be ascribed to a single body but to the system of bodies between which forces act (such as the Earth and the body that you lift up). The system's energy will indeed increase – if you are not including the lifter in your system.

(d) "[D]oes this rest frame mean that the object has no kinetic energy[?]" Yes, that's what we'd usually say. We wouldn't usually count, for example, the random motion of molecules relative to a body's centre of mass frame as part of an object's kinetic energy.

(e) "Does the rest frame also imply a specific potential energy, or does it vary depending on the object's position still?" See (c) above.

(f) In Special Relativity a body's KE can still be expressed in terms of its mass and speed: $$KE = mc^2(gamma-1) text{in which} gamma ={left(1-v^2/c^2right)}^{-1/2}$$ Regarding the KE as a function of mass and speed, since $m$ includes the body's energy relative to its centre of mass, its kinetic energy does depend on its energy in its centre of mass frame frame, and that includes the potential energy of interactions between its particles.

Note My $m$ is the invariant mass (independent of a body's speed) or simply the mass. It used to be called 'rest mass'. Anna v (see her answer) denotes it by $m_0$. I do not use the notion of relativistic mass.

All types of energy which are independent of the reference frame contribute to an objects rest mass. If you add potential energy to a spring by compressing it, its mass will increase. If you heat an object up, its rest mass increases. A system of two photons flying in opposite directions with momenta $p$ and $-p$ does have a rest mass, even though individual photons are massless.

The $E$ in the $E=mc^2$ refers to an object's rest mass energy, which is the intrinsic energy the object has due to its mass. The more general result is given by $E^2 = {bf{p}}^2c^2 + m^2c^4$, which gives you the energy for massless particles as well. All of this can be derived by solving the Lagrangian for a free particle in $Bbb{R}^4$.

For the Lagrangian coordinates ${x^mu(tau)}$ with the action given by $$S=cfrac{1}{2}mint_Gamma g_{munu}dot{x}^mudot{x}^nu dtau$$ we take the conjugate momentum, to get $$p_{mu}=cfrac{partial L}{partialdot{x}^mu}=mg_{munu}dot{x}^nu=m{dot{x}}^mu$$ Now by using the index rule we have that $p^mu=g^{munu}p_nu$ to get conservation of mass: $$p^mu p_mu=-mc^2$$ Now we switch to the Cartesian coordinates by using $g_{munu}=eta_{munu}$ to get $$cfrac{d p_{mu}}{dtau}=0$$ Since $p^mu p_mu=eta_{munu}p^mu p^nu$, we can use the conservation of mass to normalise the 4-velocity and get $$eta_{munu}dot{x}^mudot{x}^nu=-c^2dot{t}^2+dot{x}^2+dot{y}^2+dot{z}^2=-c^2$$ We can now rearrange this to end up with the following $$dot{t}^2=cfrac{c}{sqrt{c^2-{bf{v}}^2}}=gamma$$ where ${bf{v}}$ is the velocity 3-vector. Now by applying the chain rule, we can get the components for the 4-velocity. As an example $$dot{x}=cfrac{d x}{dtau}=cfrac{dx}{dt}cfrac{dt}{dtau}=gamma v_x$$ Similarly we have $dot{y}=gamma v_y$ and $dot{z}=gamma v_z$. As for the first component, we simply use $x^0=ct$. Now that we have all of our 4-velocity components, we can write $$dot{x}^mu=(gamma c, gamma{bf{v}})$$ We can now write down the momentum 4-vector, but before we do, you should know that this result was derived from considering the Lagrangian for a free particle in $Bbb{R}^3$, you should try it yourself. The full momentum 4-vector is given by $$p^mu=left(cfrac{E}{c}, {bf{p}}right)$$ Similarly, we also have $$p_{mu}=left(-cfrac{E}{c},{bf{p}}right)$$ Finally, by using the equations above and the conservation of mass, we get to the result $$E^2=m^2c^4+{bf{p}}^2c^2$$ For ${bf{p}}=0$, you get to the desired $E=mc^2$. Now bare in mind that the relativistic effects such as the particle gaining mass from being accelerated only start to take affect when sufficiently high speeds are reached, i.e. when $$1-cfrac{{bf{v}}^2}{c^2} << 1$$