Fantasy has long borrowed an idea of "another world" from myth, legend and religion. Heaven, Hell, Olympus, and Valhalla are all "alternative universes" different from the familiar material realm. Plato reflected deeply on the parallel realities, resulting in Platonism, in which the upper reality is perfect while the lower earthly reality is an imperfect shadow of the heavenly. The lower reality is similar but with flaws.
Modern fantasy often presents the concept as a series of planes of existence where the laws of nature differ, allowing magical phenomena of some sort on some planes. This concept was also found in ancient Hindu mythology, in texts such as the Puranas, which expressed an infinite number of universes, each with its own gods. Similarly in Persian literature, "The Adventures of Bulukiya", a tale in the One Thousand and One Nights, describes the protagonist Bulukiya learning of alternative worlds/universes that are similar to but still distinct from his own. In other cases, in both fantasy and science fiction, a parallel universe is a single other material reality, and its co-existence with ours is a rationale to bring a protagonist from the author's reality into the fantasy's reality, such as in The Chronicles of Narnia by C. S. Lewis or even the beyond-the-reflection travel in the two main works of Lewis Carroll. Or this single other reality can invade our own, as when Margaret Cavendish's English heroine sends submarines and "birdmen" armed with "fire stones" back through the portal from The Blazing World to Earth and wreaks havoc on England's enemies. In dark fantasy or horror the parallel world is often a hiding place for unpleasant things, and often the protagonist is forced to confront effects of this other world leaking into his own, as in most of the work of H. P. Lovecraft and the Doom computer game series, or Warhammer 40K miniature and computer games. In such stories, the nature of this other reality is often left mysterious, known only by its effect on our own world.
The concept also arises outside the framework of quantum mechanics, as is found in Jorge Luis Borges short story El jardín de senderos que se bifurcan ("The Garden of Forking Paths"), published in 1941 before the many-worlds interpretation had been invented. In the story, a Sinologist discovers a manuscript by a Chinese writer where the same tale is recounted in several ways, often contradictory, and then explains to his visitor (the writer's grandson) that his relative conceived time as a "garden of forking paths", where things happen in parallel in infinitely branching ways. One of the first Science fiction examples is Murray Leinster's Sidewise in Time, in which portions of alternative universes replace corresponding geographical regions in this universe. Sidewise in Time describes it in the manner that similar to requiring both longitude and latitude coordinates in order to mark your location on Earth, so too does time: travelling along latitude is akin to time travel moving through past, present and future, while travelling along latitude is to travel perpendicular to time and to other realities, hence the name of the short story. Thus, another common term for a parallel universe is "another dimension", stemming from the idea that if the 4th dimension is time, the 5th dimension - a direction at a right angle to the fourth - are alternate realities.
While this is a common treatment in Science fiction, it is by no means the only presentation of the idea, even in hard science fiction. Sometimes the parallel universe bears no historical relationship to any other world; instead, the laws of nature are simply different from those in our own, as in the novel Raft by Stephen Baxter, which posits a reality where the gravitational constant is much larger than in our universe. (Note, however, that Baxter explains later in Vacuum Diagrams that the protagonists in Raft are descended from people who came from the Xeelee Sequence universe.)
One motif is that the way time flows in a parallel universe may be very different, so that a character returning to one might find the time passed very differently for those he left behind. This is found in folklore: King Herla visited Fairy and returned three centuries later; although only some of his men crumbled to dust on dismounting, Herla and his men who did not dismount were trapped on horseback, this being one folkloric account of the origin of the Wild Hunt. C. S. Lewis made use of this in The Chronicles of Narnia; indeed, a character points out to two skeptics that there is no need for the time between the worlds to match up, but it would be very odd for the girl who claims to have visited a parallel universe to have dreamed up such a different time flow - from their perspective, the girl had only been gone for a few minutes though she was in Narnia for hours, and if she was making it up surely she would have spent a while longer hiding than a few minutes.
The division between science fiction and fantasy becomes fuzzier than usual when dealing with stories that explicitly leave the universe we are familiar with, especially when our familiar universe is portrayed as a subset of a multiverse. Picking a genre becomes less a matter of setting, and more a matter of theme and emphasis; the parts of the story the author wishes to explain and how they are explained. Narnia is clearly a fantasy, and the TV series Sliders is clearly science fiction, but works like the World of Tiers series or Glory Road tend to occupy a much broader middle ground.