The Answer: It didn't. It couldn't have. As far as we know, nothing can escape the event horizon of a singularity. (See: event horizon)
So what DID we see?
If you are like me, you hate when the laws of physics are violated; you want to call a space-time cop and arrest everyone involved. So how do we rationalize such inaccuracies in a way where we can sleep at night?"
This is my theory: When we see the Narada for the first time as it confronts the Kelvin, the Narada has not just escaped from a black hole's event horizon to appear in the past/parallel universe. It escaped from a slingshot event used to travel through time into the past. We are seeing the horizon to a temporal disturbance, not a black hole.

No matter what Memory Alpha says, the Narada cannot escape from a black hole. Nothing can. Even in the time of the 24th century Prime Federation, a black hole cannot be escaped from once you cross the event horizon.
Okay, to make this premise, certain things need to be understood.
Star Trek Universe before it was altered (the Prime Universe)
Star Trek Universe after it was altered (the New Universe)
The New Universe is a parallel universe split away from the Prime Universe. The difference between this and the Mirror Universe, is WE were there. We are familiar with everything that happened in the Prime Universe so the idea that it is a parallel universe is difficult to handle. But it is just another reality, out of sync with the New Universe that now comprises the Star Trek franchise.
This new Universe is separated from the Prime one and technology from the Prime Universe has contaminated the new Universe, resulting in a more technologically advanced Federation.
I hypothesize, both Prime Spock and the Narada used a variation of the "slingshot effect" coupled with the variability of the supernova and the artificial nature of the "red matter" to travel through time.
The "red matter" would allow Spock to create a gravitationally-dense enough field to use as a gravity point for a lightspeed break-away maneuver. Since the Jellyfish (his hyper-advanced ship) used transphasic shields it could conceivably have survived the stresses of a lightspeed breakaway maneuver and is fast enough to reach warp 8, a speed sufficient for the maneuver.
Using warp capable torpedoes he could use the same delivery system he would have used to deposit the red matter at the center of the supernova and instead used it to create a point for his slingshot. (How the Narada survived is a different question...supposedly it was designed to survive gravitational extremes.)
The Jellyfish experimental series of space craft were designed to be equipped with trans-metaphasic shielding which was capable of withstanding conditions that would destroy most other starships. Through the use of this form of special shielding, the Jellyfish was capable of moving through more dangerous terrain and survive it such as the interior of a star. They were designed for use by a single occupant with the vessel being the size of a shuttle craft. It contained a warp drive which was able to attain warp eight as well as two weapon arrays at the front of the ship.
This is far more plausible than the Narada escaping from a black hole since we know theoretically it isn't possible. We also know that time travel and dimensional travel were both possible in the Prime Alpha Quadrant. Difficult, requiring a great degree of technological proficiency, but completely possible.
Time travel using the slingshot effect was done as early as 2267 in the episode "Tomorrow Is Yesterday." The Federation would use this technique to travel into the past and the Enterprise crew would use it to travel in time to retrieve whales to bring back into the future in "Star Trek IV: The Voyage Home."
The slingshot effect, also known as the light-speed breakaway factor, was a method of time travel through the use of an artificially-created time warp. This maneuver was performed by traveling at an extremely high warp factor towards a stellar body with a high gravitational attraction, such as a star. After allowing the gravitational pull to accelerate the vessel to even faster speeds, the vessel would then break away from the stellar body, creating a whiplash effect which could transport the vessel through time. Performing this maneuver required extremely precise calculations to be made, such as availability of fuel components, acceleration, and mass of a vessel through a time continuum.
- Dimension travel into the Mirror Universe or alternative dimensions was also possible if difficult and had been done as early as 2267 (a good year for trans-dimension and trans-temporal travel it seems) in the prime universe TOS episode "Mirror, Mirror."
The "mirror universe" is the informal name for the parallel universe first recorded as visited by James T. Kirk and several officers from the USS Enterprise in 2267. This parallel universe coexists with the prime universe on another dimensional plane. The mirror universe was so named because many people and places seemed to be opposites of their characteristics in the prime universe, with numerous "good" aspects now "evil" and vice versa, thus "mirror-like." (TOS: "Mirror, Mirror")
Here is where we run into problems:
The original premise for the "red matter" was to create an artificial singularity which would contain part or all of the destructive force of the supernova.
The only way for this to work was to fly INTO the supernova and unleash the singularity absorbing the supernova's destructive power, in effect causing it to collapse in upon itself again...
If the supernova were already in progress, this would not stop the inner planets of the solar system from being destroyed, only those at the edge of the event.
The outer planets would not be consumed by the stellar destruction but would still perish as the star would be erased by the black hole leaving an object whose mass had to be greater than the star it replaced to be effective at curtailing the explosion at all. Perhaps this would at least allow for time to attempt an evacuation of those remaining worlds.
My theory rests on the idea that Prime Spock would have seen his use of the "red matter" fail to control the supernova and attempted to escape by using a lightspeed breakaway factor since he would already be headed into the supernova anyway. Perhaps he thought he could conceivably try again, at an earlier time, perhaps he simply sought to escape the supernova. Since he had to be flying into the nova anyway, he may have thought of using the slingshot effect at the last second.
The Narada, seeing Prime Spock's ship, the Jellyfish, would attempt to pursue him thinking he caused the event. As they follow him, they are engulfed in the space-time event Prime Spock uses to escape.
Time travel being as unstable and unpredictable as it is, the Narada arrives first appearing from what would appear to be a black hole. I posit this is more of a dimensional wormhole from one universe to the next. It CANNOT be a classic representation of a singularity because nothing can escape the event horizon of a black hole, yet the Narada appears to quite easily re-enter the new universe.
At the end of the movie, Kirk fires on the Narada as it is consumed by the ignited "red matter" when the Jellyfish crashes into the Narada because he was unsure whether the singularity created by the red matter might move the Narada to another location and survive. This implies the "singularity" does not behave completely like a black hole and may have unstable qualities which separate it from a naturally occurring singularity.

According to writers Roberto Orci and Alex Kurtzman, Kirk orders the Enterprise to fire on the Narada as it is being pulled into the black hole at the end of the film to prevent the ship from possibly emerging elsewhere and causing more chaos and destruction.
Production Notes
With all that said, know that the writers of the Star Trek (2009) have admitted taking many liberties with both the Star Trek franchise AND the laws of physics. For instance:
The writer's notes indicated the Narada is capable of surviving the intense crushing gravity found near black holes. Why? They didn't say. Some mumbling about Borg technology. Perhaps the Romulans mine neutronium or other superdense materials in their spare time.
They allowed the explosion near the end of the movie to disrupt the event horizon of the artificial singularity in order for the Enterprise to escape from the event horizon of a singularity? It warped space, er, um, something. What? That's what I said.
If you want to know more, see DarthMojo an entertainment insider for a complete rundown of how much of the movie ended up on the cutting room floor and why you still can't make sense of what you see in Star Trek (2009).