First of all... for the clueless: SMB=Super Mario Bros./SML=Super Mario Land/SMW=Super Mario World/YI=Yoshi's Island/SM64=Super Mario 64/SMS=Super Mario Sunshine/SMG=Super Mario Galaxy
The Mario brothers, Mario & Luigi, are the two plumber mascots of Nintendo. They were created by the mind of Shigeru Miyamato, a Japanese game developer for Nintendo. Their names are Mario Mario and Luigi Mario, respectively.
Mario first appeared in the 1982 arcade hit Donkey Kong, and became an instant hit. He appeared again 2 years later in Mario Bros., his first title role. This game also introduced Luigi to the public. Mario first came home on the Nintendo Entertainment System in Super Mario Bros., one of the best selling games ever. This game brought Mario into millions of homes around the world and made him a cultural icon.
Since then Mario has appeared in many other games for the Super Nintendo, Game Boy, Virtual Boy, Nintendo 64, Gamecube, Wii, and DS. A Mario (or Luigi) game has been released alongside each of these systems and helped many of them succeed. These games have consistently brought new innovations into video games and been extremely successful in the stores. Super Mario Bros. is still the best selling video game ever, selling over 40 million copies worldwide since its release. Super Mario 64 has been hailed as "The greatest video game of all time" by Next Generation magazine, and critically acclaimed on countless occasions. Past that, New Super Mario Brothers (DS) has performed greatly, getting one of the highest marks to be found from Nintendo Power in their review of it. It, and other Mario games, have received countless awards.
The Mario bros. have become a cultral phenomenon outside of video games. They have been featured in 3 cartoon series, one major motion picture, and every toy imaginable, from board games to water guns. He's been featured in many non-game magazines and been a topic in a few widely published books. In an old 1991 poll, it was found more kids could identify a picture of Mario than Mickey Mouse. He has also outlasted most of the mascots from his era.
This page (and site) has everything else you'd ever want to know about the Bros. If it isn't on this page you can always e-mail Kyle with any questions and chances are he would know the answer.
Misconceptions
It's been noticed a lot of people have outright wrong information when it comes to some areas of Mario knowledge. This section tries to remove these knowledge-impaired people's misconceptions. All of the info here is as accurate as possible, using the games as the first source, and other sources only when absolutely necessary. So read on, and learn something
Naming
The Mario Bros. consist of Mario Mario and Luigi Mario. They are the Mario Brothers because their last name is Mario. This is why it isn't the Luigi brothers. (Note: This has been confirmed by Miyamato-san himself.)
The character in the original DK was originally referred to as Jumpman when the game was in preproduction (some Japanese translation no doubt). By the time the game came into production in the US, though, the character was known as Mario. Therefore, it is acceptable to refer to Mario or Jumpman as being the star of DK. However, the main character in DK3 is not Mario, but an exterminator known as Stanley the Bugman.
Toad is the royal mushroom retainer of the Mushroom Kingdom. Not all the little mushroom guys are "Toad", as they are other citizens of the Murshroom Kingdom. Everyone calls them Toad anyway (Go figure). They might all look the same to us, but I'm sure there's some slight differences to tell them apart. =)
The Princess' name is Princess Peach Toadstool. The first name is Peach and the last name is Toadstool. That is why she is called Princess Peach in Japan and the letter at the beginning of SM64 is signed "Peach". Similarly, it is King Bowser Koopa. The first name is Bowser, and the last name is Koopa. This settles the double name issues.
Princess Peach isn't the only princess Mario has saved. In Super Mario Land, (and the Mario Movie, andthe comics) Mario saved Princess Daisy instead. In Donkey Kong, neither of those. It was Pauline instead, a damsel in distress taken captive by Donkey Kong. Mario's exact relationships with these three women is sketchy at best... but Mario seems to especially like Peach (and she baked him that cake at the end of SM64... so bonus points!) Pauline has only appeared in one game since her debut, Mario vs. Donkey Kong 2. Peach, on the other hand, has appeared in countless titles, and even had her own game (Super Princess Peach.) Daisy usually appears only in the multiplayer games--so it is obvious Peach is the main relationship with Mario.
The name Yoshi refers to the one specific, green dinosaur that Mario saves in SMW. The term "Yoshi" also refers to the whole species of multi-colored dinosaurs. There is only one "Yoshi" though. (confused yet?) The other Yoshis (besides the main green one) are often called Yoshi's "cousins" although this doesn't seem to be a traditional, family relationship, but more like a general title (e.g. "father" used to refer to a priest). The baby Yoshis found in eggs are not all children of the one, green, "Yoshi", but rather, babies of one of the Yoshi species of dinosaur. Understand? No? Didn't think so. But that's as clear as it can be made here.
Wario, and hence, Waluigi, have sketchy relationships at best with Mario. Wario is not Mario's 'evil twin' nor is Waluigi Luigi's. Wario and Waluigi themselves, however, are related.
Super Mario RPG was partially made by Square; therefore, many characters remain exclusive to it. Characters such as Geno or Mallow, therefore, are unlikely to appear in any future games. The game itself has not had any direct sequels as a result of this, either. However it itself has 'Spiritual' successors, such as Paper Mario and its own sequels.
The Mario brothers' origin is hotly debated, and therefore, it is difficult to place their origin. Some games say he was delivered with Luigi by a stork (See Yoshi's island), while others reference a New York connection (Donkey Kong, Mario Bros.) however it appears the Yoshi's Island version is more prevalent, and likely to be the main game storyline for now. (Some games, however, like to play with this idea.)
Settings/Storylines
The true "Mushroom King" (Peach's father, not the 7 kings in SMB3) is never mentioned in the games. He only takes form in the Nintendo Adventure System comics as a sort of ignoramus, who is basically just a figure-head, while the Princess does all the real ruling. It's as good an explanation as any.
The Mario bros. have been presented as plumbers, construction workers, and even demoltion workers at various points in their pre-princess-saving career. As Kyle would say, "I like to think of them as general contactors, doing all sorts of work around the home from time to time. That's just my opinion though." The games stay away from Mario's occupation after SMB, however he later does such things as acting as a doctor, plays tennis, races, etc.
SMB take place in the Mushroom Kingdom. This is the gateway to the Mushroom World, where SMB3 take place. Each "world" in SMB3 is a different country of the Mushroom World. SMRPG also takes place in the Mushroom World. Although all three (including SMB2 in Japan) have a Mushroom Kingdom, none of them look the same. The world of Mario changes much, so it can be safely assumed that the games take place in different sections of the Mushroom World, and that is prone to changing quickly over time.
SMB2 is totally outside of the storyline of SMB and SMB3. It takes place in Sub-Con and is not made by the Mario team. It was originally Japanese game called Doki Doki panic with Indian characters. The programmers slapped Mario characters in there and bam, a new game. This is why none of the old SMB enemies are in it. SMB2 in japan actually picks up where SMB left off, and has similar play to SMB. It was released here in SM all-stars as the "lost levels". Strangely enough, the further Mario games retain some SMB2 (U.S.) enemies, which must have seemed new to the Japanese gamers who hadn't played it. The strange world of SMB2 is explained as being one of Mario's dreams, so it is likely we won't encounter it again.
In a similar way, SML was not made by the Mario team. It was not supervised by Shigeru Miyamato. This is why it has differences from the other Mario's, such as hearts instead of 1up mushrooms and strange enemy names. It takes place in Sarasaland, so the differences are forgivable storylinewise (as it's a totally different place). Furthermore, these differences do not effect future games.
Super Mario World take place in Dinosaur Land, which, coincidentally, has eight sections for the Koopa Kids to take over, as did SMB3 =). Yoshi's Island is one of these sections of Dinosaur Land. It is also the setting of Yoshi's Island (Duh) but has a lot more areas than the SMW Yoshi's Island, presumably, because it is set earlier than SMW.
SML2 take place in Mario Land, which has been turned to Wario Land by Wario. What is Mario land? How'd Mario get a land? Where is this land? Who knows. Maybe he got so much money from all those coins he bought his own land. SML3 take place place on Kitchen Island. I don't know how they got a statue of the princess there (in the ending), but, eh, whatcha gonna do.
Various other worlds are shown. There is a Mansion created by Boos in Luigi's Mansion, Isle Delfino (with its various sections) in Super Mario Sunshine, Rogueport and its surrounding environs in Paper Mario 2, and so forth. All of these areas appear to be mutually exclusive, but occasionally games in different areas refer to past ones.
Mario isn't really fighting all those other characters in Super Smash Bros. According to the game's intro, all the characters are really dolls brought to life. Furthermore, they are trophies in Super Smash Brothers: Melee.
Disregard any storylines put forth by books, TV shows, or movies featuring the bros. They are all so mixed up it's not even funny. Trying to connect the games story and Hollywood's will give you a headache, so just forget about it.
Spin-off character relationships
Wario's relation to Mario is very unclear, as stated earlier. Some stories say that they're childhood chums (the NP comics for instance), while some say they are brothers (Wario being the evil twin), and there's even one account saying Wario comes from another dimension. The similar naming (changing an "M" to a "W", how original) is odd, for sure. After the events of SML2 (and the ending of SML3) Mario and Wario part paths, and Wario makes quite a few cameos. Wario doesn't really seem evil (Not in the way Bowser is) but his extreme greed leads him to do horrible things. One can't really think of one "bad" thing he's done that wasn't prompted by money (Except in the inexplicable Wario's Woods). Speaking of Money, he has recently appeared in many games involving even more money-making schemes (the Wario Ware series), so it is likely he doesn't entirely work for evil.
Yoshi is a dinosaur that lives on Yoshi's Island in Dinosaur Land (with a summer home in Yos'ter Isle in The Mushroom Kingdom (SMRPG)). He is NOT Mario's pet (Neither is Poochie, while we're on the subject). While Yoshi and Mario have had a special bond since the events in Yoshi's Island, it is not an owner/pet relationship at all. Yoshi helps Mario because in SMW he was also mad at Bowser (for trappnig him and all of his kind in eggs) and because Mario saved him.
Waluigi appears to hate Luigi, but doesn't seem to care about Mario. Unlike Wario, he appears to definately be evil, especially with the strange things he's done (attacked during a tennis tournament, stealing... music keys?) and he is definately Wario's younger brother. He has very few appearances, making one wonder if he was too young to appear in some of the earlier games.
A number of strange characters appear in the RPG games. Smithy, for example, took the Mushroom Kingdom by storm. He fought in only one game, though. Another one-hit wonder is Grodus, who appeared in Paper Mario II. Following him are the Shroob and also Cackletta. All of these foes only appear in the RPG games, however, and so their stories remain simple: They usually displace Bowser in doing something, and Mario must fight them. Few of them recur within the Mario series, so it's best to play the games they're in rather than to spoil their stories here.
There are many other characters in the Mario series. In fact, too many to list here. However, most of them have relatively simple stories.