"Thank you Mario! But our princess is in another castle!"
Super Mario Brothers was developed by Nintendo (with the legendary Shigeru Miyamoto as lead developer) and published in the US for the NES in November 1985. (It was released in Japan on September 13, 1985, and in Europe in 1987.) The game (as of this noding) is quite possibly the most common game available for the NES; Super Mario Brothers was the pack-in game with the NES for most of its life, until Super Mario Brothers 3 eventually replaced it. Because of this, it's available as a dual-cart with Duck Hunt, and as a triple cart with Duck Hunt and Track Meet.
The ROM is readily available and complete, and the game has been rereleased for the SNES in Super Mario All-Stars (August 3, 1993 in the US and July 14, 1993 in Japan, with a later rerelease as Super Mario All Stars + Super Mario World as part of an SNES pack-in) and for the Game Boy Color as Super Mario Brothers Deluxe (August 4, 1999 in the US, and, curiously, March 1, 2000 in Japan.) Super Mario Brothers is also one of the flagship games in the Famicom Mini rerelease of the NES launch titles on the GBA; as part of this series, a straight (perfect, glitches and all) port was released on the GBA on June 7, 2004. SparroHawc informs me that Super Mario Brothers is also hidden in Animal Crossing as a minigame, but does not, as yet, know how to unlock it.
Super Mario Brothers is the grandfather of one of the most venerable genres in video games: the platformer. (Specifically, the sidescrolling platformer, but all other platformers are based on the original 2-D sidescrollers.), not to mention the second great hit for one of the greatest producers in video game history, Shigeru Miyamoto, the original killer app for one of the longest lived consoles in history, the NES, and quite possibly the game that revived the console game industry after the Atari crash. While Nintendo used VCR-like styling and accessories like R.O.B. the Robot to fool retailers into stocking the NES, Super Mario Brothers, coupled with intelligent marketing and word-of-mouth, gave the NES the beginning of the momentum that would run strong for nearly 8 years.
Almost everyone who has played video games has played Super Mario Brothers or one of its sequels. Mario's popularity has even been compared to Mickey Mouse, and the opening bars of each of the Mario themes are firmly lodged in popular culture (as well as techno remixes probably until the end of time).
Better information on the history of the NES, as well as Mario's later adventures, can be found in Nintendo Entertainment System, Nintendo, and Mario. In addition, there is a subtly different arcade version of Super Mario Brothers, known as Vs. Super Mario Brothers.
As for the story, the game's manual says it all...
One day the kingdom of the peaceful mushroom people was invaded by the Koopa, a tribe of turtles famous for their black magic. The quiet, peace-loving Mushroom People were turned into mere stones, brick and even field horse-hair plants, and the Mushroom Kingdom fell into ruin.
The only one who can undo the magic spell on the Mushroom People and return them to their normal selves is the Princess Toadstool, the daughter of the Mushroom King. Unfortunately, she is presently in the hands of the great Koopa turtle king.
Mario, the hero of the story hears about the Mushroom People’s plight and sets out on a quest to free the Mushroom Princess from the evil Koopa and restore the fallen kingdom of the Mushroom People.You are Mario! It’s up to you to save the Mushroom People from the black magic of the Koopa!
While this story seems primitive now, it's certainly a step above "a monkey has kidnapped your girlfriend" or "you're being attacked by marauders held aloft by balloons!" and shows the beginning of a move away from the arcade game design to what would become console game design. Super Mario Brothers has linear progression in the stages, which allowed for something of a story, rather than the infinite loop or infinite uphill progression of the arcade games of the time.
Mario, as well as his green-clad brother Luigi (who was controlled by the second player), on his own, had a surprisingly large repetoire of moves for a character of the time. Besides running and simply jumping over foes, he could jump into the air and stomp on enemies as he progressed through the strictly left-to-right stages. Not only this, but Mario could swim, rising upward by rapidly tapping the jump button (with controls exactly like Joust or Balloon Fight), and, by jumping up and bumping the bottom of blocks, enemies on the top can be defeated. In fact, by bumping the bottoms of flashing (or sometimes even just normal-looking) blocks, he could receive coins or one of the Mushroom Kingdom's special plants.
Of course, Mario's sundry talents were nothing compared to the powers that the flora of the Mushroom Kingdom could give him. If he got a Super Mushroom from a block, it would turn him into Super Mario, twice as tall and able to break blocks by jumping up and punching them. (No, he didn't hit them with his head.) Not only that, but subsequently touching a Fire Flower gives him the ability to toss deadly fireballs. He could even get an extra life from the appropriately named 1-up Mushroom. Finally, while it wasn't exactly a plant, a Starman, a shining star as big as Mario, could grant him temporary invincibility if touched, allowing Mario to barrel through his enemies like Pac-Man eating ghosts.
His foes had many variations, but most of them were the members of the Koopa Troop, known, appropriately, as Koopa Troopas. The Koopa Troopas, malevolent turtles that they are, couldn't be killed by simply hopping on their heads. (The shells weren't proof against fire or Starman invincibility, however.) If he did that, the Koopa Troopas would simply retreat into their shells, safe and sound. However, Mario can kick these shells, sending them flying and knocking out other foes like bowling pins.
The stages were something of a revolution at the time as well, as Mario wanders through a variety of environments. Each of the eight worlds is divided into four stages. The first three stages of each world were set in a variety of locales; Mario wanders the fields of the Mushroom Kingdom, goes spelunking in its many caverns, swims through its lakes and rivers, and even leaps through its skies, defying death as he hops from platform to platform.
The final stage of each world, however, was one of the many castles in the Mushroom Kingdom, ruled over by what appeared to be Bowser himself. however, through the first seven of the eight worlds, upon defeating this imposter Bowser (by pelting him with fireballs, which revealed his true nature, or by grapping the axe behind him and cutting the lines to the bridge), all Mario rescued was one of the Princess's Mushroom Retainers, infmaous for their single common message. "Thank you Mario! But our princess is in another castle!" The real Bowser, hiding away in the eighth world, was standing guard over the Princess personally, of course.
While many of the bugs in Super Mario Brothers are noded elsewhere, the game had a number of secrets that were intentional (or at least not design flaws.)
- At the end of each stage is a flagpole Mario grabs to end the stage. If you grab the flagpole when the timer's ones digit is 1, 3, or 6, you get that many fireworks, each firework burst being worth 500 extra points.
- The game had a hidden continue option. After a game over, simply hold A when choosing between one player or two players. You will restart at the beginning of the world you died in.
- In Super Mario Brothers, after 8 consecutive "bops" on the heads of enemies, each additional bop would earn Mario another life. World 3-1 had an opportunity for infinite one-ups, near the end of the stage, because of an opportunity to get an infinate number of bops. On the "staircase" of blocks leading up to the final jump to the flag, there were a pair of Koopas. Simply stomp the second one, then land on the shell again, kicking it into the staircase. If you timed things right, the shell should rebound, and Mario should land on it again, kicking it into the staircase again. Repeat until you have all the lives you want.
- Hidden in several underground stages are "Warp Zones", a series of pipes taking Mario to another world entirely.
- World 1-2 had a warp zone to Worlds 2, 3, and 4, accessed by riding one of the platforms near the end of the stage up to the row of bricks that form the "ceiling". Hop up on these bricks (Mario will be on the same level as the world number, timer, score, etc. - this is normal), and walk all the way to the right.
- World 4-2 has a warp zone to World 5, accessed in much the same way. After getting on top of the ceiling, just bypass the stage's ending to get to the Warp Zone.
- World 4-2 also has a block, seemingly out of reach. Below this block is an array of hidden coin blocks. By carefully hitting only the correct blocks, Mario can jump up and bop the out-of-reach block, causing a vine to a Warp Zone to grow. This Warp Zone has pipes to Worlds 6, 7, and 8.
Upon beating the game the first time through, "Another adventure" was available, which is basically the game game with increased difficulty from more enemies and tougher enemies, as well as often-frustrating enemy placement. Not only this, but you could choose what world to start on in the second play through, by hitting B on the title screen to advance through worlds. (For example, one tap for World 2, two taps for World 3, etc.)
Major thanks to TheBooBooKitty for history and perspective. Much of this info is distilled from GameFAQs and the Killer List of Video Games, as usual, as well as a misspent youth.