Also see Donkey Kong Beta Elements.
Before a game gets released you might see enemies and places that aren't in the released game, because they are taken out for unknown reason. The elements that were once in the game but were taken out are called Beta Elements.
Beta Elements
Here is a list of Beta Elements appearing in Mario games:
Super Mario Bros. 3
There were going to be two new enemies called Gold Cheep Cheep (a golden version of a Cheep-Cheep, and Green Parabeetles (green colored Parabeetles). The Gold Cheep Cheeps would come in groups and swim faster than regular Cheep-Cheeps and the Green Parabeetle is a green Parabeetle that flies faster than normal ones.
Koopa Troopas and and Hammer Bros. were going to host the mini-games. They were replaced by Toad. There were also different kinds of mini-games, similar to the ones in New Super Mario Bros..
Super Mario World
Dinosaur Land was drastically different, possessing an appearance similar to the various kingdoms of Super Mario Bros. 3. Specifically, it was to feature things such as Toad Houses (which could possibly mean that Toads were once considered to populate Dinosaur Land) and more Super Mario Bros. 3-style Fortresses.
SNES test cartridges also exist, and, among other things (some of which are Mario-related), they include an early build of Super Mario World. These cartridges reveal that, at one point, Goombas were to be able to be stomped (even earlier test cartridges show that Goombas also once possessed their normal, mushroom-like appearance rather than the Goom-like Goombas seen in the final game and later builds), Koopa Troopas were to walk on all fours, and normal Piranha Plants and even Venus Fire Traps were to have been present. Interestingly, several of these cartridges' beta sprites were merely simple Super Mario Bros. 3 edits. Lastly, the Super Leaf and Raccoon Mario form were both present in early builds.
Super Mario World 2: Yoshi's Island
This game was going to have more forms Yoshi could turn into-a Mushroom, a Tree and a Plane (replaced by a helicopter). The game was also going to feature Tweeters and Green Bob-ombs.
Super Mario RPG: Legend of the Seven Stars
Looking into the coding of Super Mario RPG: Legend of the Seven Stars reveals several unused enemies (most of which seem to be unused sub-species), including a notorious one known as the Drill Bit. In fact, Drill Bit appears in the game, but does not fight in any battle like a normal enemy.
Super Mario 64
In the Beta version, it would've had a numbered health bar instead of the pointed one. Many stages and bars would be different. Thwomp would also have a scarier look and Mario would have a different jump (one that let him spin around after a triple jump in a way similar to the result of being hit by a Tweester in Shifting Sand Land). There would also be a tanish Cheep-Cheep. Mario was voiced differently (possessing a screechy, childlike voice rather than his current Italian accent) and Bowser sounded more tiger-like.SourceSource 2 and 3Source 4
Paper Mario
Early screenshots of this game showed that Poochy was going to play some sort of role in the game. Another screenshot showed that Nep-Enuts were going to be in this game also. Also the early version of Forever Forest showed that it would be much smaller, with all the forest's trees having sinister faces.
Yoshi's Story
It seems as if Flowers were going to appear in the game, which was once called by Yoshi's Island 64 Screenshot. Also, Big Guys were going to appear and Bone Dragons would be purple, flesh-covered dragons rather than bony, undead ones. Finally, Stage 4-2: The Jungle Puddle was known to be much scarier, with strange bubbles and a Bone Dragon.
Mario Kart 64
Kamek or a Magikoopa was going to be in this game playable, but got replaced by Donkey Kong. Also note that the Character Select Screen was going to be very different.
Super Mario Sunshine
In Super Mario Sunshine, Delfino Plaza is the main plaza of the game. However, in movies before release, it showed that there was going to be a different plaza (or possible prototype for Delfino Plaza), with a giant Strollin' Stu-like creature walking all over the place, and many more different things. A Human girl was going to appear here, wearing a pink dress. It is unknown whether she was important or not or what she was doing. She may have also been a citizen. Also FLUDD was going to be skinnier and Gooper Blooper was going to be dark blue and fought on top of the bridges of Ricco Harbor instead of in the market and helicopter area. Source
Mario & Luigi: Superstar Saga
Wario, Fox McCloud, Captain Olimar, Samus, an Excitebike Racer, and Link were going to show up in the Starbeans Cafe after Mario and Luigi made coffee, instead of E. Gadd (who was going to make an appearance, but only one).
Mario Power Tennis
In the intro of the game where Wario and Waluigi are drawing on the scorechart in the left the player can see Toad and Toadette's heads. It is unknown if they were going to be playable and they forgot to take their faces of the scorechart.
Paper Mario: The Thousand-Year Door
There were many unused badges. See Badges for information on them.
The partners from Paper Mario were going to appear but we're cut-off as well. Bow and Parakarry were the only ones left. There was also a strange robot-like creature.
Mario & Luigi: Partners in Time
In this game, there were going to be some Blooper enemies appearing in the Vim Factory wearing red shoes. While the screenshot only showed Luigi attacking one, it isn't known what their attacks were.
Super Mario 64 DS
Several beta screenshots were released for the game. Originally, all four characters could fight Bowser at the time and could fly. Most of these features were later turned into Mario-only abilities.
Super Princess Peach
The Koopalings were originally going to be in the game, but were taken out for unknown reasons. All of the Koopalings' lost sprites have been discovered by now. Oddly enough, Morton's sprites were spread around the internet long before those of his siblings.
New Super Mario Bros.
The working title for this game was Super Mario Bros. DS. Also, during early stages of production, Mega Goombas were going to be a generic species (the result of a Goomba colliding with a Super Mushroom and powering up) rather than an individual boss. (It is possible that other enemies were to be compatible with this situation, too, considering the giant enemies like Super Dry Bones and Super Piranha Plant that remain in the game in generic, already-large forms.) There was also said to be a Mario and Luigi co-op mode at a time. Interestingly, an illustration of beta map icons still exists as a screenshot on page twelve of the final game's manual. There also was an underwater stage which also featured Manta Ray in VS. Mode.
Yoshi's Island DS
As stated below, Yoshi's Island DS was originally going to be compatible with Nintendo Wi-Fi. Also, one early screenshot showcasing a battle with Big Guy the Stilted seems to suggest that Big Guy was once going to be organic, as he had no patches on him in that picture (although one patch was visible near his right foot, which may merely mean his graphics were slightly incomplete). Finally, one screenshot of an unknown origin shows a Black Yoshi traversing a flowery area with Baby Peach. The particular event illustrated in the picture doesn't seem to be left in the final game.
Wi-Fi
Many Mario games were originally going to have Nintendo Wi-Fi; however, it was taken out of some. Mario Hoops 3-on-3 and Yoshi's Island DS (known as Yoshi's Island 2 back then) were the two games that were going to have Wi-fi.
Gallery of Beta Images
- Koop.gif
A Koopa Troopa hosting an item mini-game. - Hammer.gif
A Hammer Bro. hosting a card mini-game. 
A beta screenshot of Dinosaur Land from Super Mario World. 
Another screenshot of the beta-version of Dinosaur Land. 
The Drill Bit of Super Mario RPG fame. 
The Magikoopa that would have once been playable in Mario Kart 64. 
A beta Bone Dragon (that is actually alive) from Yoshi's Story. - PaperPoochy.jpg
A beta-screenshot of Paper Mario with Poochy in it. - PaperNep-Enut.jpg
A Nep-Enut as seen in a beta-screenshot of Paper Mario. - Gooperbeta.JPG
Gooper Blooper's "beta-version", Mario's health bar also looks different than in the final version of Super Mario Sunshine. - Tramplin' Stu.jpg
A giant Strollin' Stu-like creature, cut out of Super Mario Sunshine. Also note that there's another, different beta health bar. - Old FLUDD.jpg
FLUDD's old, thinner design. - Beta.jpg
An unused human citizen of Isle Delfino. - Old Plaza.jpg
An unused plaza on Isle Delfino. - Gauge.gif
The bizzare, unused gauge-robot from Paper Mario: The Thousand-Year Door. 
The bizzare shoe-wearing Bloopers from Mario and Luigi: Partners in Time. 
Unused Box art for Super Mario 64 DS. - Flying.JPG
All four characters flying in an early promotional screenshot. - All4.PNG
All four fighting Bowser under the castle. - Whomp Attack.jpg
A Giant Whomp attacking Mario and Luigi. Also note the blue box from Super Mario 64. - The Original NSMB.jpg
The Original opening title of New Super Mario Bros. - Rope Land.jpg
Some type of rope land. 
The Mega Goomba species. - Giant Manta.jpg
An unused underwater stage. 
The unused Koopaling sprites from Super Princess Peach. - Double Trouble.jpg
Notice the designs of the item boxes and Spindrift. - Yidscreen6.jpg
A Yoshi's Island DS beta battle with Big Guy the Stilted, who lacks mechanical features here.
