If you want to experience Mario really old school like some of us did who started on Atari...here's the path we underwent from hearsay and gaming mags about the games as they came out.
Once upon a time, there was a gorilla who kidnapped a girl and a carpenter named Mario (a.k.a. Jumpman) literally jumped at the chance to rescue her. - Play Donkey Kong arcade or NES version. Or Donkey Kong Original edition NES that has the missing stage.
Mario beat Donkey Kong and put him in a cage. His son decides to pull off his own rescue of dear old dad from the evil Mario. Yes, that's how people used to describe Mario at that one point in time during the DK Jr. era, EVIL MARIO - Play Donkey Kong Jr. Arcade or NES, Famicom, Famicom Disk System version. I don't think there's a NES version that has the missing stage.
(Optional) Donkey Kong hides out in a greenhouse perhaps in an attempt to evade Mario and a guy named Stanley tries to drive him out with bug spray. No one ever hears from Stanley again so I assume Donkey Kong won and Stanley gets eaten alive by bugs. - Play Donkey Kong 3 on arcade or NES.
Mario after his humiliation at the hands of DK Jr., gives up carpentry, goes into the plumbing business with his brother Luigi but they end up acting more like exterminators as they try to get rid of endless sewer pests on the pipes they're working on. Play Mario Bros. on Arcade or NES
While cleaning up the pipes in Mario Brothers, Mario finds a letter during this time from a mysterious Princess Toadstool begging him to rescue her kingdom from the evil Koopa a.k.a King Bowser. who transformed the inhabitants of her kingdom into stone, bricks and plants. The letter mentions she hid some magical items hidden in ? blocks to aid Mario in his quest. With his brother Luigi, they find a pipe that led to the Mushroom Kingdom. - Play Super Mario Brothers on NES or the Japanese Super Mario Bros 2/Super Mario Bros. the Lost Levels that happens in an alternate reality. Or better yet, just play Super Mario All Stars on the SNES to get the near entirety of Mario's 8 and 16 bit legacy.
Back in the day, I only played Doki Doki Panic and the Japanese Super Mario Bros. 2. I only got to play it when I got Super Mario All-Stars much later but I'll put this in anyway. Mario dreams of a land called Subcon and a vague message calling for help about someone named Wart who hates vegetables. During a picnic with the recently rescued Princess Toadstool, her retainer Toad and Luigi, they find a cave that leads to Subcon and are catapulted into a new adventure...which turns out to be all a...(see ending) - Play Super Mario Bros 2 U.S. version
Bowser returns with his seven children, the Koopalings (before it was all retconned) to invade the seven kingdoms of the Mushroom world and transforms all the reigning monarchs into random beasties. Mario and Luigi must now battle Bowser, his army, their new arnaments and save everyone. Play Super Mario Bros. 3.
For the rest of the other games, just follow what the other posts are saying but I'm adding one more part just to complete the above saga.
After several adventures in the Mushroom Kingdom, Mario discovers that Donkey Kong has returned and has kidnapped his old girlfriend Pauline all over again. In a strange twist of déjà vu, Mario finds himself reliving a battle he thought was long behind him. But this time, something unexpected happens… Play Donkey Kong for Game Boy a.k.a. Donkey Kong '94.
