This character hardly needs introduction. If you have a Wii or any other Nintendo console, chances are you know him, and maybe you have even bought one of those consoles because of him. If Super Smash Bros. had a lead character, it would be him: Mr. Nintendo himself, Mario!
Like in many other games, Mario is the most well-rounded character in Project M. Mario has no glaring weaknesses; he has average running speed, aerial mobility, weight, and Wavedash length. His basic attacks are fairly quick, have little endlag, and have a variety of uses ranging from setting up combos to creating space between him and his opponent to getting knockouts at decent percents. His Fireballs give him good zoning and approaching options and his Cape keeps from being zoned by projectiles himself. Even his recovery is deceptively good, taking into account that Mario can use his Cape, Mario Tornado, and walljump out of Super Jump Punch to gain considerable distance! However, this all means that Mario isn't particularly effective at any one thing, either. He isn't as fast as Sonic, doesn't control space as well as Snake, doesn't combo as well as Sheik, and doesn't kill as well as Ganondorf.
In Project M, Mario is a mix of both his Melee incarnation and his Melee clone, Dr. Mario; he takes the best from both characters and integrates them into a single moveset that will both remind Mario and Doc mains of their respective characters and create one of the most effective incarnations of this iconic character seen in a Smash game.
Mario's specials also underwent very little changes with the exception of one move – the F.L.U.D.D. was taken out entirely and replaced with Mario's old Down-Special: the Mario Tornado, which functions exactly like the version in Melee. Mario's Fireballs have a trajectory between Mario's normal Fireballs and Dr. Mario's Megavitamins. The Super Jump Punch remains the same, with the exception of the fact that Mario can now walljump out at the end of it like he could in Melee, improving his recovery on most stages significantly.
Mario's combo game is very straightforward but effective. He has lots of good combo starters, some of his more common ones being his Neutral-Air, Down-Air, Up-Tilt, and either his Down-Throw or Up-Throw depending on the weight/fall speed class of the character Mario is facing. Either one of his throws are very good since they can both set up for killing blows at good percents; use Up-Throw on heavyweights and fastfallers and Down-Throw for everyone else. Fireballs of course are a good tool to help Mario close distance safely and can even set up combos in their own right. Up-Tilts and Up-Airs are the bread and butter choice for continuing combos, and most of Mario's long strings will most likely contain many chained Up-Airs. Mario's Forward Air is the best choice for a combo ender, particularly the Doc hit, although the Mario hit can set up for tech chases if he's close enough to the ground. If the opponent isn't outright killed, Mario can use his good edgeguarding game to keep opponents off of the stage. Fireballs can be used to force the opponent to recover lower, while Back-Air can send the opponent at a deadly angle that most won't be able to come back from. Cape is also invaluable at keeping opponents offstage, being able to reverse the direction of recovery options and incapacitate most of them.
Though this is a bare-bones guide to basic Mario combos, this is far from everything Mario has to offer. He is such a versatile character that many different variations and approaches to comboing and taking stocks are all viable and will most of the time work to varying degrees. It highly depends on the player to make use of all the potential Mario has to offer, and how that player chooses to apply it determines his success.