Current high-power lasers focus light to intensities up to 10^23 times higher than the intensity of sunlight at the surface of the Earth. At these extreme intensities the electrons are quickly stripped from the atoms in any matter in the laser focus, generating a plasma. However, as intensities increase from the peak reached today (2x10^22W/cm^2) to those expected to be reached on next-generation facilities such as the Extreme Light Infrastructure (10^23W/cm^2), due to become operational by 2017, the behaviour of this plasma dramatically alters. At intensities 5x10^22W/cm^-2 the electromagnetic fields in the laser focus are predicted to accelerate the electrons in the plasma so violently that they prolifically radiate gamma-ray photons. These photons can carry away so much energy that the electron's motion is affected by the resulting energy loss and the radiation reaction force (the force the particle exerts on itself as it radiates) becomes significant in determining the plasma's macroscopic dynamics. The laser's electromagnetic fields are so strong that quantum electrodynamics effects also become important. In this case the radiation reaction force no longer behaves deterministically, i.e. instead of knowing the electron's trajectory exactly as in the classical picture, we now can only know the probability that the electron has a given trajectory. In addition, the gamma-ray photons can be converted into electron-positron pairs, these pairs can emit further photons which emit more pairs and an avalanche of antimatter production can ensue with strong consequences for the behaviour of the plasma as a whole. The interplay of radiation reaction, QED effects and ultra-relativistic plasma processes will define the physics of laser-matter interactions in this new 'QED-plasma' regime, but is currently poorly understood. We will elucidate the basic theory of laser propagation and absorption in QED-plasmas. This will provide the foundational theory describing laser matter interactions moving beyond today's intensity frontier and into the foreseeable future. This theory will be underpinned by experiments measuring the rates of the important QED processes for the first time. The new theory will then be used to design the first experiments to generate a QED plasma in the laboratory. This project will culminate in the first generation of a QED-plasma, usually only seen in extreme astrophysical environments such as pulsar magnetospheres, in the laboratory.