Someone called Ditto McCloaker of the Gamehiker forums thought up this really cool origin story for both Mario and Wario.
It said that there was this magical circus that went from our world to the Mushroom World (because Italy was known for it's circuses and Mario does this whole acrobatic act in the intro of DK '94) where Wario's father was the ringmaster. He and Mario's parents were good friends and he showed them the the place where he got all the strange performers in his circus (the Mushroom Kingdom), which is where they chose to move. Then hey had kids and the events of YI followed, thus causing them to hand them over to Wario's father to keep them safe. So, over the years they were raised by him, and built up a rivalry with his kids, Wario and Waluigi. (This explains why Mario is such a good acrobat and could also explain how he met DK, who may have been a circus animal at that time.)