It begins in the 30's during the Great Depression. Mario and Luigi are arriving on a boat into New York Harbor. They, like legions of other immigrants had a grand, idealized notion of America, but they arrived in a bad place at a bad time. Jobs are hard to come by, and though they start a plumbing company, neither of them really know what they're doing. Furthermore, in a desperate attempt to find work, they take the worst, dirtiest jobs the city has to offer.
One day, Mario is busy trying to trace the path of a pipe to find a leak. He goes deep into the recesses of an old building. Even at the basement, he finds himself squeezing through rotted, mildewed wood until he's far underground. A spongy bit of boarding gives way, and he drops into what looks like a cave. There, he sees the pipe bottom out, but curiously, it's surrounded by large, colorful, strange-looking mushrooms like things out of a fairy tale. As he digs to try and pry one out of the dirt, something else begins tugging the mushroom from underground. The dirt collapses, and he falls headfirst down a pitch black hole. First he can feel the dirt around him, but soon he's in free fall. After what feels like the sensation of suction and a bright light, he's shot out.
Cut to Dinosaur Land in a similar manner to Dorothy arriving to Oz.
In front of him is the mushroom, which he picks up while staring in dumbstruck awe at the fantastical surroundings. His first thought is that he's either dead or dreaming, yet he's soon called to attention by an angry, squat-looking creature stomping towards him. It looks like a turtle only it's wearing a helmet and walking on two legs. It's also jabbering in an unintelligible language, pointing at the mushroom in Mario's hand. He's about to hand it over too, but the turtle's face goes red, and it begins to charge. Mario closes his eyes and turns his head, flailing his arms, eventually feeling his fist come into contact with something along with a rather noisy clunk. When he turns around, the turtle is lying unconscious. It's at this time that dozens of other creatures, smaller still and looking much like the mushroom in his hands surround him. They prattle off in a similar language but seem friendly enough - ecstatic even. A few stand around the turtle, jumping for joy and cheering. The rest grab Mario's arm, pulling him off to one direction.
Letting them lead him along, they eventually reach a small village deep in the woods. Dozens more pop out of their dingy, little houses to see what's going on, and upon hearing the news also begin to celebrate. They're all quieted though when an older mushroom man opens the door to a larger building at the far end of the village. He beckons Mario to come, which he does, and on entering the house is surprised to see a human woman in an elegant gown sitting at a table. Someone too has tried his or her hardest to make the scruffy place presentable as well - even decorating the table with candlesticks and faded rugs upon the floor. Mario has said nothing this whole time, so it's the woman who speaks first, doing so in English surprisingly enough.
She is the princess of the Mushroom Kingdom - or what is left of it. Like Mario, she fell through a strange hole; only she was a child at the time. The mushroom people took a liking to her, and she eventually decided to stay, enjoying the fact that she has her own fairy tale world to explore. Yet after a few years the fantasy was broken. The Mushroom Kingdom was invaded by a greedy yet dimwitted lizard named Bowser who fancied himself a king. He and his kind were once kappa, inhabiting a little river until Bowser caught a glimpse into another world. He saw castles with high walls and warriors clad in metal who served a king draped in jewels and furs. Convincing the rest of his people to follow him out of their home waters and cast down their spirithood to look for wealth and build their own kingdom, they became things resembling lizards, "Koopa" as Bowser called them. When they discovered the Mushroom Kingdom, Bowser decided that he wouldn't have to build anything at all when he could steal from others.
The mushroom people weren't warriors, so the princess gave herself a title and decided to defend her adoptive home and friends. Yet mostly all they had been doing was running, moving farther and farther back into the forest. The koopas, for all their bluster were hesitant to pursue them, for fear of whatever could lurk in the trees, and there the mushroom people stayed with their princess. Until Mario knocked out one of the koopas' soldiers, they had never had seen any victory.
Mario wasn't that strong though, so even he was surprised he took down the turtle in one punch. He did however feel stronger while holding the mushroom. Apparently some of them held magical properties, the princess said. The koopas horded them, and maybe without them, they'd lose their power. Maybe he always pitied the little guy, but for whatever reason, Mario decided to help fight Bowser.
