For Mario, there's 3 things that are critically important to learn: learning to combo, learning to grab, and learning to edgeguard.
1) Grabbing
Grabbing with Mario is by far one of the most difficult things to do. Ever. It's also something you have to have a knack for, because 75% of his combos come from grabbing (the rest from f-air setups or u-tilt hits)--so if you don't nail a grab on the opponent, your damage output gets significantly lower.
That being said, grabbing is a pain because Mario's grab range is pretty lousy. He has to get extremely close to grab without any help at all (i.e. from stuff such as projectile rushdown like Doc/Falco or good spacing like Marth/Ganon). Even worse, nearly every character above Mario has some move/quality/trait that nullifies Mario's grab-- Fox/Falco has their Shine that stops shieldgrabbing as does their speed/rushdown, Marth has his long-range sword spacing, Sheik has her speed and practically no-lag aerials. . .the list goes on and on.
So how do you grab? You basically have to mindgame them into it. Dashdancing into a jump-cancelled grab is pretty standard. You can also spot-dodge -> grab, or shieldgrab, or wavedash -> grab (really good against Marth), techchase -> grab. . .you have lots of options available.
The thing to remember here is twofold: one, most of the characters you'll play against will always have something to nullify Mario's grab. And two, you'll need to find a way around that, because if you don't grab, you don't get damage output (from your combos). Throughout the match, you should be thinking at every second "what can I do to grab him." I'd go even as far as saying that your goal shouldn't be to KO the opponent--it should be to grab. (An exaggeration, but you get the point).
2) Combo'ing
Okay, you've grabbed the *******. . .so now what?
At this point, you already know about your combo tools: u-throw for fastfallers, d-throw for heavies/floaties. U-tilt can chain into itself; if they DI that, you can go into shffl'd u-airs to follow their DI or go with dash -> jump cancelled u-smash. That's the basic gist of it.
As an aside, my personal favorite is Eggz-style u-throw -> full-jumped rising d-air -> falling fastfalled u-air -> (land) shffl'd u-air -> sex kick finisher. U-throw to the d-air is pretty decent on floaties at low %s, and is a nice mix-up from your standard d-throw chaingrab/techchase options.
Anyways, I also want to point out that contrary to popular belief, Mario's combo game is crap. His combos revolve around his u-airs, but anyone who knows how to DI can DI down and away from that and tech, so they can escape it pretty easily. . .especially Marth (who can f-air out of it), and floaties (who can sex kick out of it), and fastfallers (where it's difficult to set them up for u-air chains at the perfect angle/%).
What this means is that you have to start relying on techchasing out of botched combos to get the maximum damage output you want. Let's say they manage to DI correctly and escape the next u-air in your u-air chain. You know they'll tech, so you anticipate that, and instead of doing another pointless u-air, you guess whether they'll tech left/right/in place, and aim a shffl'd f-air at where they'll land, thus setting them up for another combo.
You'll have to learn to techchase properly, especially with shffl'd f-air, jump-cancelled u-smash, and grabs, as these all help continue combos (since they're all vertical launchers). You can techchase with other less combo-oriented stuff too (like d-smash, shffl'd sex kick) which you may want to start off with, since shffl'd sex kicks are much easier to aim.
3) Edgeguarding
Mario's KO potential is pure crap, as I'm sure you've realized. F-smash is a fairly good move, but it's more for spacing than anything else, since it's certainly not as spammable nor as easily combo'd into as half of the other KO moves in the game (think Marth's f-smash, Falcon's knee, Sheik's f-air, etc.)
You then have to rely on another means of KO's: namely, edgeguarding. It's a firm belief of mine that Mario should be EXTREMELY aggressive when it comes to edgeguarding. You should be willing to jump off the stage. Go ahead and do crazy, unconventional stuff to throw off the opponent. Do anything, as long as you keep the ******* away from the edge.
I'm pretty sure you have a good enough idea of what edgeguarding with Mario consists of. B-airs off the stage are his edgeguarding bread-and-butter; you can perform them any number of ways, from an edgehog -> drop down -> double jump b-air -> up-b recover to other stuff like wavedash off the stage -> cancel edgehog with a fastfalled b-air into the opponent -> double jump -> up-b recover. Stuff like that. You can try b-air'ing in the opposite direction to knock them into the side of the stage to stage spike them, but only if you think they can't tech properly.
Besides off-the-stage stuff like b-airs and sex kicks, there's also on-the-stage stuff that you can always pull off that'll deter your recovering opponent. Shffl'd f-airs at the edge can spike them (though it's not normally recommended since everyone knows how to meteor cancel), shffl'd d-airs work well in disrupting some recoveries (namely Falcon/Ganon's up-b and Fox/Falco's side-b), down-angled f-smash/f-tilt (these are REALLY good; don't underestimate the down-angled f-tilt even though it has no knockback), d-tilt (especially at opponents at high % since it's a perfect setup for a sex kick finisher), and even the kick of Mario's AAA ground combo (the kick actually has a huge hitbox that goes underneath the stage, even more so than his d-air).
And don't forget the cape and fireballs for random pseudo-spikes.
Don't be afraid to experiment and goof around with edgeguarding. Mario can often pull random stuff out of his *** to edgeguard; it's really one of his strengths. Just remember that your main source of KOs will usually be through edgeguarding, so take care to do anything possible and keep your opponent off the stage once you get him off.
).