In the beginning, Jerry Siegel gave Superman's amazing physical strength a "scientific explanation": Superman came from a planet "whose inhabitants' physical structure was advanced millions of years of our own."  As the planet is destroyed, the being who will become Superman rockets to Earth to begin a new life. That origin has been altered slightly over the years, but the core remains: alien life, space travel, and evolutionary advancement—Superman is a science fiction story.
Or at least Superman stories, since the beginning, have had the trappings of science fiction. But the appearance of some of the genre conventions doesn't necessarily indicate that the stories are really science fiction. Taking a look at several definitions of the genre  reveals that, by the standards of many of the genre's writers at least, there must be something more than the trappings, more than space ships and laser guns. That something more is often an illumination of the human condition. Themes often revolve around societal or individual verities that might otherwise be unexplored in a genre where aliens don't live among us, where interstellar travel or teleportation are still impossibilities, or where ultimate truth is still a mystery and technology is terribly mundane by our standards. In other words, science fiction offers an extrapolation of a scientific principle that explores human nature. Do Superman stories do this?
That's a difficult question to answer, because there are a lot of Superman stories. The only medium in which there are a manageable number is film, with five entries if we exclude the old serials. There have been monthly comic books (sometimes weekly, and of course the daily newspaper strips) published since 1938, adding up to millions of pages of stories. Then there are the television shows, both live action and animated, the novels, the video games, the lunch boxes, and the stories that come with action figures.
Let's limit ourselves to a few recent stories and focus on All Star Superman, a self-contained narrative which ran for twelve issues from 2005 to 2008. All Star alludes to stories from virtually every era of Superman's history. It garnered the highest awards the comics world has to offer, and was consistently a top-selling title. The story, written by Grant Morrison, drawn by Frank Quitely, and inked and colored by Jamie Grant, chronicles the last days of Superman on Earth as he discovers that he has only a limited time to live, having been poisoned by Lex Luthor. He struggles with the knowledge of his coming end, trying to ensure his legacy and the safety of a world without him. The "world without Superman" theme has been a recurrent one in Superman comics. In this comic, we don't see that world, but the story that leads up to it. The story contains the three science fiction motifs mentioned above—aliens, space travel, and evolutionary advancement—and a host of others. It seems sufficient to use as a case study for the science fictional aspects of Superman, but we may have to pull in a few other examples along the way.
So what kinds of themes does Superman explore? That depends on who's interpreting the stories. Many people have referred to him as the ultimate immigrant,  thus representing the fundamental American experience. Others have called him the anthropomorphic realization of our highest hopes and dreams. Let's blend those together: Superman is an alien, and he is something greater than human but within human fantasy. He looks human, after all. And yet he has come to Earth, and mingles with human beings. Larry Niven was perhaps the first to take this idea to the inevitable conclusion in his famous essay "Man of Steel, Woman of Kleenex,"  which really must be read to be believed. Essentially, it postulates the true consequences of Superman's love for Lois Lane, in graphic detail. It's best not to think about poor, poor Lois in this situation.
And yet. . . .
Superman and Lois did get married, in 1996, in the comics. This coincided with their marriage in the television series Lois and Clark: The New Adventures of Superman. Despite this, their potential for offspring has only been explored in the movie Superman Returns. In that film, it is implied that Lois Lane was impregnated when Superman had given up his powers in Superman II, and the pair was able to consummate their relationship. Somehow, however, the boy has super strength. The logical gaps in this plotline make it easily forgettable. Science fiction, we must remember, pays more than a passing attention to real science.
Superman and Lois Lane, or any other human woman, would be unable to produce children because of his alien genetics (an issue not discussed by Niven) which are incompatible with humans. It's the same reason dogs and cats can't reproduce. Horses and donkeys can; however, the result is a sterile mule. They're close, genetically, but not a true match. Superman may resemble a human, but that, as Niven points out, would be merely the result of parallel evolution.
This is all beside the point anyway, because Morrison, in All Star Superman, has perhaps given us an alternative to the traditional way to create a Kryptonian-Human hybrid—genetic engineering. One of the recurring motifs of the series is the mapping of the genome. It comes up in nearly all of the twelve issues. In the first, the only character Morrison invented specifically for this series, Leo Quintum, tells Superman that he's "trying to escape from a doomed world . . . the past." His method is to build a race of superhumans who could replace Superman should the need arise. In All Star Superman, the need is imminent. Quintum's assistant, Agatha, is attuned to genetic codes. She describes Superman's as "like Bach. If only we could find a way to crack the Kyrpton code, we could grow a second Superman."
By issue 10, Superman's overdose of solar radiation is starting to weaken him. He knows the end is near. He has managed to keep it a secret from the rest of the world, but Quintum has told Lois. She confronts him, and says she knows he'll find a way out of this. When she asks him to promise he'll survive, his response is that their biology is incompatible.
"We could never have children," he says. "Never have more than this."
"There's always a way," Lois responds. "That's what you always say."
His survival is, at least in this exchange, only relevant insofar as they can have a marriage and a family, only insofar as their lives can end with children. There's always a way.
Also in this issue, we learn that Superman has not only copied his own genetic sequence for Quintum, but also devised a way to combine human and Kryptonian DNA strands. In the same panel as this is revealed, Superman's narration, in the form of his will, tells us that "To Lois Lane. . . I leave our future." The implication is obvious by this point: Quintum is going to combine Superman's genes with those of Lois Lane.
The series ends with Leo Quintum reassuring Agatha that the world will not be lost without Superman. He "knows how it's done," he tells her, and points to a modified version of Superman's sigil, with a 2 instead of an S. Superman can, essentially, be reborn in his offspring with the information he has given to Quintum. Quintum's success is foreshadowed in issue 2, when Lois stands in front of Superman's Time Telescope, a device for corresponding with the future which is still far from finished, but useful enough to get "cryptic messages." She is confronted by the Unknown Superman of 4500 AD, who allows her to question him. She asks: "Will . . . Superman and I ever marry and have children?" The cryptic response: ". . . The horrible. . . zzzxxttt. . . answer is before you. . . ." The Unknown Superman is one of Superman's descendants, more of whom we meet in issue 6. So the answer, literally standing before Lois, is yes, sort of. They may not marry, but they will have children. The last time Lois sees Superman—after he's defeated Luthor and must fly to the sun, which has been poisoned—she is holding his cape. The cape, in many versions of the story including the most recent, is actually Superman's baby blanket. So she'll have something to keep the children warm.
Those children will determine human history. Humans become something greater with the addition of Kryptonian genes. The general state of humanity in the future is undisclosed, but it's safe to say that such enhancement wouldn't be unpopular. Who wouldn't want to fly, have super strength and senses, and become immune to most forms of harm? The end result of Superman's life, it seems, is to make the rest of humanity like him.
Uplifting humanity in such a way, enhancing evolution, has been a theme of many science fiction stories, in particular two very popular series: Arthur C. Clarke's Space Odyssey books (and the two films), and David Brin's Uplift series. Both of these series postulate that sentience as humans know it may be the result of the tampering of proto-humans by an alien species. In 1968, the same year that 2001 debuted, Erich von Daniken's book Chariots of the Gods  tried to make the case that such tampering had occurred in reality, that the gods of ancient myth are actually aliens who laid the seeds of humanity aeons ago but returned at intervals to ensure that evolution toward consciousness and sapience proceeded apace. Clarke and Brin have very different ideas about the cause and consequence of the alien intervention, but both fiction authors offer the extrapolation and consequence for humanity that marks true science fiction. Is the story of Superman, as it has evolved and as it has been expressed in All Star Superman, so different?
In a way, yes. Superman begins with a different premise, a different extrapolation to explore. Essentially, it begins with first contact, as the result of an alien species' last hope for survival as the planting of a single seed on Earth. It then builds to the logical conclusion: that in order for that seed to reproduce, some sort of hybridization must occur. Genetic engineering provides the means.
Consider the tangentially related story "The Heart of a Star," by Neil Gaiman and Miguelanxo Prado.  In it, in the early days of the universe, the stars and nebulae and the things that come before gods get together to have a meeting. In one conversation, Despair tells the star Rao (around which Krypton orbits), "Wouldn't bringing life onto a planet that is inherently unstable add to the beauty of the life? If at any moment it would explode. . . .Truly it would only be perfectly beautiful, a perfect piece of art, if one single life-form escaped. To remember, to mourn, to despair." Here, Superman's defining characteristic is not flight or morality, but the mourning and despair arising from the destruction of Krypton. He is alone among people who are like him.
Such a being would crave the company of his own kind. In Superman Returns, he journeys to the ruins of Krypton so that he can know for sure he is alone. In the comics, he finds comfort when other Kryptonians arrive on Earth. Some have argued that both of these are antithetical to the character and the story, but the impulse behind his actions is consistent. In All Star Superman, he solves the problem by finding a way to reproduce. It's the same thing anyone in the situation might attempt. The difference is, Superman can make it happen. He always finds a way.
That fits. The main result of the creation of Superman, by Jerry Siegel and Joe Shuster, has always been inspirational. Children love the character. The powers, the morality, the creed . . . these have all become, in words that have become common, part of the mythology of America. Mark Waid, sometime writer of Superman comics, has even written about the inspirational effect Superman had on him. He's not the only one. Even Superman comics have commented on this. Take "What's So Funny about Truth, Justice, and the American Way?"  Superman must fight a vigilante group called the Elite, a group that kills villains instead of capturing them. Before the fight, Superman tells Lois why he has to confront them: "I heard a child tell his friend that he wanted to be in the Elite because it would be fun to kill bad guys. Fun to kill. People have to know that there's another way, Lois. They have to hear a voice of compassion and faith instead of spite and anger. They have to see that someone believes in humanity strongly enough—." "To die for them?" Lois finishes.
In the end, Superman defeats the Elite, and in doing so makes it appear that he has had to resort to their own methods instead of his own. Thinking that his friends are dead, the group's leader Manchester Black breaks down in tears in front of the cameras that have captured the event. Superman reveals the trick, saying that he wanted to show the world what it would be like if he crossed the line, how ugly the world would be. Black promises to get revenge, telling Superman, "If you think this is over, you're living in a bloody dream world!" Superman says, "I wouldn't have it any other way. Dreams save us. Dreams lift us up and transform us." He promises to make his dream a reality, the dream of truth, justice, and the American way.
The American element has provided ideas for authors to engage in different kinds of speculative fiction as well. DC Comics has often engaged in "imaginary stories," or "elseworlds," in which their characters are placed in alternative realities (alternative to the DC Universe where they traditionally live, that is). In these stories, the authors explore the ramifications of various scenarios: What if Superman were raised by apes? What if Superman had landed in Russia instead of the US? Kim Newman even wrote "Ubermensch," a prose story that imagined Superman having landed in Germany.  The list goes on.
Saying that all Superman stories qualify as science fiction wouldn't be entirely accurate, despite the presence of science fiction motifs and conventions. Many of them are traditional adventure stories, or perhaps more appropriately classified as sci-fi, since many of them choose not to explore themes related to human nature or the "something more" that many writers insist as a component of true science fiction. Some are straight fantasy, with no attempt to anchor the story to any technical or scientific development. These are not judgments, but rather interesting facets of the stories that can be told with the character.
Superman is periodically "reinvented" to more fully fit the tastes and ideals of the changing times. Kelly's "What's so Funny about Truth, Justice, and the American way?" is an attempt to demonstrate Superman's relevance during the trend toward darker, more violent heroes. But Morrison, discussing All Star Superman, says: "I don't think we need to 'make' Superman relevant. We just have to tell stories which resonate with human experience. The best Superman stories are fables about love, pride, shame, fear, death, friendship, etc. We can all relate to those big issues. Superman stories should represent huge, basic human dramas and human emotions, played out on a larger than life canvas."  The character is versatile and can accommodate virtually any genre conventions that creators wish to employ, from romance to mystery, fantasy, and science fiction. Perhaps this is what makes the character mythic.
 Jerry Siegel and Joe Shuster. Action Comics Issue 1. Collected in The Superman Chronicles, Vol. 1, 2006.
 A collection of definitions of science fiction gathered from many famous writers in the genre can be found here.
 Grant Morrison, Frank Quitely, and Jamie Grant. All Star Superman, 2 Vols. 2008-2009.
 Danny Fingeroth, Superman on the Couch: What Superheroes Really Tell us about Ourselves and Our Society; Garth Ennis and John McCrea, Hitman, Issue 34, 1999.
 Dennis Dooley and Gary Engle, eds., Superman at Fifty: The Persistence of a Legend, 1987.
 Larry Niven, "Man of Steel, Woman of Kleenex." The Man from Krypton: A Closer Look at Superman, edited by Glenn Yeffeth, 2006. It is also online.
 Arthur C. Clarke's series is comprised of four novels: 2001: A Space Odyssey; 2010: Odyssey Two; 2061: Odyssey Three; and 3001: The Final Odyssey. The first two were adapted into films. The series is based on ideas from several of Clarke's short stories, notably "The Sentinel." Brin's Uplift series is actually six books, any one of which is probably longer in word count than the whole of Clarke's series. It begins with Sundiver (1980), then Startide Rising (1983), The Uplift War (1987), Brightness Reef (1995), Infinity's Shore (1996), and Heaven's Reach (1998).
 Erich von Daniken, Chariots of the Gods, 1968.
 Neil Gaiman and Miguelanxo Prado, "The Heart of a Star" is in the collection Sandman: Endless Nights, 2003.
 Waid has written about this in an article called "The Real Truth about Superman: And the Rest of Us, Too" in Superheroes and Philosophy: Truth, Justice, and the Socratic Way, edited by Tom Morris and Matt Morris, 2005; and also on his blog.
 Joe Kelly, Doug Mahnke, and Lee Bermejo, Action Comics, issue 775, 2001. It is collected in The Greatest Superman Stories Ever Told, Vol. 2, 2007.
 Millar, Mark, etc. Superman: Red Son, 2009; Superman/Tarzan, Sons of the Jungle by Chuck Dixon and Carlos Meglia, 2002; Kim Newman's "Ubermensch" is collected in The Year's Best Science Fiction: Ninth Annual Collection, St Martin's Press, 1991.
 The original text of this interview, which was conducted by Newsarama, is no longer available at that site. The quotation I have included can be found at Fanboy Rampage and at Kevin Beaucoup (Dot) Com.