I know that the theory of relativity is E^2 = (mc^2)^2 + (pc)^2

And when a particle is at rest it has no momentum therefore p = 0 and we arrive at E = mc2

 

But how did Einstein arrive at E^2 = (mc^2)^2 + (pc)^2 first.

The formula you stated is a consequence of special relativity and gives the total energy for a moving body in a particular frame. The mathematics of special rel uses 4 vectors where the time component features on equal footing as the spacial ones (except it is multiplyed by the speed of light for dimensional consistency). A useful result of using 4 vectors is when you multiply one by itself (using the 4 vector scalar dot product) you get a quantity that is invariant - that is, it has the same value in any frame.

 

The mass/energy formula that everyone harps on about can be derived from the invariant you get from dotting the momentum 4 vector with itself. There are many more invariants such as dotting the velocity 4 vector with itself etc.

 

If you haven't covered vectors yet then try this (scroll down about 1/2 way). Or try here for a small rel course covering 4 vectors.