I've said plenty of times that Peach and doubles are the only things I care about in Smash 4. So, I was pretty excited about the title of this topic. Then, I read the OP and I got even more hype, since I'm undefeated with a Mario main in doubles (we lost once going other characters). I am literally the best person on the planet to help you with this, haha. :D I've posted a lot about my thoughts on Peach in doubles, but I'll start with some videos.
I've posted this video here multiple times. It was the ending to my first tournament ever, Grand Finals, Game 3, last stock.
https://www.youtube.com/watch?v=lV87nmf_cZs
Here's the twitch stream of Winner's Finals and Grand Finals:
http://www.twitch.tv/nuhuhx/v/4974326
WFs at 1:46 and GFs at 2:37
Here's a long video compilation of us on For Glory Teams (so team attack off obviously), where we got a 50 game win streak, that you can skim through to get some ideas:
https://www.youtube.com/watch?v=RWXdREmVnoM
Anyways, watch whatever you want from that large collection of Peach/Mario doubles gameplay. Now for some tips and advice... I play Peach as an ASSist to Mario. Both of us are extremely aggressive, 100% offensive players. You need to be an aggressive, crazy fast Mario to work well with Peach, as in using all of his utility and playing Mario the fun way that he should be played, lol (Going for Capes, FLUDD, Spikes, crazy juggles, ect.). Doubles allows you to go for high-risk/reward play-styles, as long as your partner can BACK you up.
And Peach is the perfect biatch to back it up, lol. As Peach, I will always be ready for any kind of possible follow-up and 2-on-1 edge-guard I can get that Mario sets up for me. Parasol is OP af in doubles, especially with a Mario that can juggle characters up high easily, which nets early Parasol kills for Peach. Use team attack to your advantage for juggles as well. Who cares about damaging your teammate, when it'll get you an early kill (like the first video I linked). So, basically I like to float above the action a lot, and wait for these opportunities. For example, if I see Mario is in the process of edge-guarding someone, I'll float above him, while he's charging FLUDD, and I'll either help him edge-guard with Fair, or I'll Bair the opposing teammate that's trying to save their partner, and let Mario finish the edge-guard himself. Always cover both options for 2-on-1 edge-guards. If I go low, he'll cover high with a Spike. If I go high, he'll cover low with either cape, FLUDD, or another spike if they're hugging the edge.
Mario's Back Throw is very good in doubles, as he usually "beats a mother****er with another mother****er" lol. Peach can usually hit a Peach Bomber during the swinging animation as well, which is another really good move in general for doubles. A combo we like to do (as you'll see in our online compilation video at 2:20), is having Peach float behind and slightly above Mario when he's Back Throwing someone, Bair, and then have Mario jump and spike the opponent. Peach's Bair has a lot of hit-stun and a huge hitbox, which makes it another great move in doubles. At higher percents, just having Peach floating far away when Mario has a grab, following up Mario's Back Throw to Peach's Bair will kill pretty easily. Just gotta learn the placements and percents for those situations.
I could go on and on about combos with this team, since that is what this team relies heavily on, but what's most important is just overall team chemistry. You guys will be naturally creating your own team combos, if you have enough chemistry. Don't force roles or "fundamentals" when it comes to doubles. Team chemistry is the foundation of doubles.
The only teams that give us a problem are extremely defensive teams. However, it's doubles, so the way to get through their defense is to just stay together as a team, and don't get separated into 2 1v1 matches. There aren't any specific characters that give us any trouble.
Lastly, as far as stages go... just ban Battlefield. Pretty much our only game losses have been on that map. The platforms and overall lack of space kills our movement and combos. Any other stage works fine (Smashville and T&C seem to be the best). Final Destination, just like in singles, is usually just match-up dependent (like characters with projectiles, strong zoning, etc.).
Otherwise, I think that's everything for now. Sorry if this wall of text was too much ;p lol. I just get really hyped and passionate about teaming with my Mario friend!