Funny thing is in one shape or fashion there is a story in every game. Story being merely a substitute word for the goal of the game. For example, In Final Fantasy, the point in the very end of each game regardless of the narrative before the events is to fight through such and such amount of battles to save the world. So the creators created plot and drama to make the venture more interesting. (Being a Final Fantasy fan it's fun to notice the game technically doesn't change, you just get there differently)
Old school games only needed a simple story like Save the Princess in Mario's case, and they didn't need to add more and more to it, but as you've noticed with more recent iterations of the Mario franchise, the story is more complex, there are more characters, and there is slightly more depth to the happenings in these worlds.
Stories in games are basically what the fuck your doing in it, so yes, story is just as important as the game-play, because it's what your doing. The story represents the idea of what you spend the game doing, and the game-play is just how the developers implemented or expressed that idea.
I don't know how many people would play a game about jacking off, even if the game-play was really fun, and conversely not many people would play a game with Lord of the Rings caliber story telling and game-play reminiscent of Pong. There needs to be a balance between the two, however there are plenty of games that lean to one or the other side and still do well.
StarCraft and Halo Final Fantasy and Mass Effect
