The Hawking radiation may be interpreted as the creation of particle-antiparticle pairs near the horizon. This is the same activity of "virtual particles" that is happening all the time in empty space – and it contributes the loop diagrams to the vacuum energy and other things. The particle-antiparticle pair normally re-annihilate rapidly, their existence is short-lived.
But in the vicinity of the event horizon of a black hole, it may happen that one particle in the pair leaves the black hole – and it is interpreted as a particle of the Hawking radiation. The other one (one which has a negative energy) has to be reabsorbed by the black hole because its momentum goes in the opposite direction, inside. Its being inside prevents it from reannihilation with the partner that is flying away from the black hole: nothing can leave the black hole interior anymore.
These two particles in the pair are entangled. For example, their spins have to be entangled because of the angular momentum conservation law. Let's assume that we just discussed a Hawking particle of the early radiation. What we have seen is that "some degrees of freedom" that were carried by the infalling particle in the pair were reabsorbed by the black hole. It follows that the outgoing early radiation Hawking particle is entangled with some degrees of freedom in the black hole.
But these degrees of freedom ultimately have to be transmitted to the later Hawking radiation, too. Because the early Hawking particle was entangled with the black hole that was left, and the black hole that was left is going to turn into the late radiation, the early radiation is entangled with the late radiation.
This attempt to explain the entanglement doesn't mean that I endorse the existence of the AMPS paradox. No such paradox exists in quantum gravity but this assumption about the entanglement isn't the problem that would invalidate the AMPS paper. This entanglement indeed does exist as AMPS assume.