Well, Metroid has the advantage of a manga dedicated to Samus's origins. And it helps that the games actually have a continuity, which I believe is unique in Nintendo's major series. Oh yeah, and Fusion had long monologues and conversations with a (sentient) computer that divulged quite a bit of backstory.
I do see your point, Trashman, but it's still fun. There isn't much to the story, but we will discuss what there is, dammit!
Mario: Save the princess! (again, for the fourth bloody time)
Oh, she's been saved much more often than four times... so often it's become a running gag in the series that if the princess even appears in a game, she
will be kidnapped, no matter how tangential to the main conflict it is (assuming, of course, that it isn't the main conflict in the first place).