Yup, paralyzer has its uses against Mario, but use it sparingly. Get used to the Mario tornado's range, you should be able to guess where it's gonna land once you get used to the match-up, and it can be downsmash punished pretty easily if you know he's gonna whiff. You can beat a lot of his grounded moves with downsmash too, just make sure you're spaced well. Depending on the flow of the match and how campy the Mario player is, powershield those fireballs! Seriously, get in your opponents mind, powershielding all of his fireballs is pretty easy to time, and it can make you opponent get impatient, forcing them to come in. Stay on your toes though, you don't want to get grabbed because you shielded too much. Get used to the timing of punishing Mario's back roll too, it's easy to punish on reaction, just dash attack it, it's definitely one of the easiest rolls in the game to punish. Zair is a good option when he's tossing out fireballs in the air, but you have to be careful, getting the full 6% off of the zair isn't easy, so you're likely to only be getting 3% per hit, which isn't worth it if you mess up. Finally, nair is one of the most important tools you have against Mario, if you're spaced correctly he CAN'T hit, or grab you. If you're missing too much then you might be doing something wrong, you should be able to more often than not land your nair on him. it's definitely the "right" way to play the neutral game. You've got more range than he does, take advantage of it.
After thousands of matches online and some tournaments, I've never struggled with Mario, you've got this! Good luck.
P.S. Sorry if this is written like each thought just popped into my mind and then I wrote it down over and over again, but that's exactly what happened =P
