Of the ones I've played, I'd rank their stories like this:
1. Skyward Sword - My personal favorite story of any Nintendo game. Charming until the end, great characters and it's the only Zelda game where I actually cared for Zelda herself. The story kept me engaged until the end.
2. Super Paper Mario - For a Mario game, this game's story is surprisingly deep, and also pretty dark at times. It develops itself very well throughout the game.
3. Majora's Mask - What's cool about this one is that it's not really about the main story, even though that's also great. It's about all the little sidequests and the self-contained stories of every NPC you interact with during the 3 days before the moon falls. Pretty melancholic at times too, but I consider that a plus personally.
4. EarthBound - It's a pretty standard story on the surface (The power of friendship and all that), but it's the weirdness about everything in it that sticks out to me. It's pretty heartfelt and I really wish that I could play Mother 3 officially since I hear that one is even better.
5. Pokémon Platinum. I know, you can't get more "stock" with a game's story than a Pokémon game. But even though I barely remember the story, I do remember really liking it, so it probably did something right =P
