Mario is one of the characters I like to play mid-range against while controlling center-stage. MK at mid-range puts a lot of pressure on Mario to approach, defend, or Fire Ball as Mario lacks safe mid-range options. (MK has Dash Attack & Dash Grab for mid-range punishes.) Mach Tornado beats Mario's Fire Ball and forward roll options, dash grab beats shield, an empty jump forward can also beat Fire Ball at Mid and nets MK a grab combo. At 0% I like to D-Throw > Up-Smash since Mario's odd weight and fall-speed makes it about the only thing guaranteed at 0. Nado from throw is heavily DI dependent but it's guaranteed if they DI Up. After about 30% it becomes safe to Up-B off of throws or go for Up-Air chains. When Mario's coming back down from a combo, if he attempts to D-Air or anything above you, Up-Tilt and Up-Smash beat all of Mario's aerial options except air dodge but air dodge is beat by Mach Tornado if you want to throw one out as a mix-up or prediction. Also MK's Dash Attack is good for everything as usual.
If Mario starts to combo you, DI Upward+away and jump away from him. Don't be intimidated by Fire Balls. MK's 6 Jumps beats any projectile and, like I said before, an empty jump forward beats Fire Ball at mid-range and leave Mario open for punish. Mario's KO options are limited to Smash Attacks, F-Air, and Back Throw very late, which makes playing mid-range even more potent against him since he has no safe KO moves unlike MK's F-Smash. When Mario's recovering, running off-stage and B-Airing as he Up-Bs can be a fairly easy gimp since it seems to still send him downward if the 3rd hit misses and can stage-spike if it connects.
That's all I've got off the top of my head. It's an even match-up until KO percent where MK just has a slightly easier time getting the KO than Mario. The hardest part of learning the MU is realizing your options against Fire Ball and that they are no threat to MK on-stage.
