The Mario Brothers are described as Italian brothers who are plumbers, not native inhabitants of the Mushroom Kingdom.
How did the Mario Brothers first discover and enter the Mushroom Kingdom?
For purposes of this question, the live-action movie is not canon.
It would seem that any origin-plot, if any, can only be derived from cross-referencing the various game.
As Valorum already said, the original NES/Famicom Super Mario Bros game didn't give out many details - we just know that Mario set out to save the Mushroom Kingdom and Princess ---Toadstool--- Peach, but we don't really know were he came from.
This plot point - Mario origin - was never touched in the main games for a while, so for the time begin the only possible answers were to be drawn from the related material such as comics, the animated shows, Choose-your-adventure game books and so on.
Most of this related material seem to indicate that the Mushroom Kingdom is intended as a different dimension and Mario came there using a warp pipe (see above comments about the animated show. Not only it specifies that Mario and Luigi found an access to the Mushroom Kingdom while performing some plumbing job, but it actually also shows Bowser trying to use the pipes to launch an attack on the human world multiple times).
This is somehow coherent with the games in a way: even before the Super Mario Bros game Mario appeared in another game, called just "Mario Bros" (even before he appeared in other games as well, Donkey Kong begin just one example, albeit the character wasn't always called Mario in those). Here Mario is "fighting enemies he came across while performing his job as a plumber" (will try to find an actual transcript/screenshot of the original manual), so while there is no official in-game reference that I know of, it seems plausible that in the original NES era Mario was indeed intended to be an Italian plumber (possibly living in America) that came to the Mushroom Kingdom using a warp pipe he found "sometime, somewhere".
This is somehow confirmed by some old Miyamoto claims/interview where he says he had Mario live in New York and that he gave him an Italian origin because of his mustache.
Then the SNES came out, and we got Yoshi Island. In this game we control Yoshi, who is trying to bring back a baby-version Mario (and baby Luigi, who was kidnapped by Kamek) to his parents-to-be after a stark "lost" them after begin attacked by Kamek. This seems to indicate that "baby" Mario was born in the Mushroom Kingdom - the game ending even show him begin delivered to an house... and while I may be mistaken that doesn't exactly look like Italy.
(notice: on the left, original storyboard for the SNES game ending. On the right, the same clip, taken from the DS remake "Yoshi NEW Island" instead)
Even later the plot only gets cloudier. Games like "Mario&Luigi: Partners in Time" seem to confirm that the "baby Mario" timeline is the same as the adult Mario one, but even later games throw in another curve ball as we discover that the world we see in the "Paper Mario" series is not just a different art stile for the same world but actually a whole alternate dimension altogether (Mario & Luigi: Paper Jam).
I would assume that right now the only real clue is in the original intent that seems to derive from the first games (and was actually somehow reused in a very unlucky movie...) as I fear that no more though has ever been put into this.
After all, they only relinked all the Zelda franchise years after the original games were made, so I fear that hoping for an official source on Mario origin inside a game may be a lost cause.
The original backstory for Super Mario Bros is laughably short. Mario heard that the Mushroom Kingdom was in danger and set out on a quest to free it. No information is given about his mode of transport to the Kingdom, nor whether he lives in the magical world normally or traveled there from the human world.
OBJECT OF THE GAME/GAME DESCRIPTION
One day the kingdom of the peaceful mushroom people was invaded by the Koopa, a tribe of turtles famous for their black magic. The quiet, peace-loving Mushroom People were turned into mere stones, bricks and even field horse-hair plants, and the Mushroom Kingdom fell into ruin.
The only one who can undo the magic spell on the Mushroom People and return them to their normal selves is the Princess Toadstool, the daughter of the Mushroom King. Unfortunately, she is presently in the hands of the great Koopa turtle king.Mario, the hero of the story (maybe) hears about the Mushroom People's plight and sets out on a quest to free the Mushroom Princess from the evil Koopa and restore the fallen kingdom of the Mushroom People.
You are Mario! It's up to you to save the Mushroom People from the black magic of the Koopa!
The Game & Watch version manual features a backstory that is even more terse (but undeniably cooler due to the inclusion of funky pictures)
turned into bricks - so Mario is killing members of the Mushroom Kingdom, and the coins are probably just whatever they had in their pockets. Man, that game turned dark quickly.
– Wayne Werner
Jun 14 '16 at 13:46
The manual for the Super Mario Bros Deluxe (GBC) adds in some more detail:
Once upon a time, the peaceful Mushroom Kingdom was invaded by the Koopa, a tribe of turtles famous for their dark magic. These terrible terrapins transformed the peace-loving Mushroom People into stones, bricks, and ironically, mushrooms then set their own evil king on the throne. In the wake of the ghastly coup d'‚tat, the beautiful Mushroom Kingdom fell into ruin and despair. It is said that only the daughter of the Mushroom King, Princess Toadstool, can break the evil spell and return the inhabitants of the Mushroom Kingdom to their normal selves. But the King of the Koopas, knowing of this prophecy, kidnapped the lovely Princess and hid her away in one of his castles. Word of the terrible plight of the Mushroom People quickly spread throughout the land, eventually reaching the ears of a humble plumber. The simple, yet valiant Mario vowed to rescue the Princess from King Koopa's tyrannous reign. But can Mario really overcome the many obstacles facing him and become a true hero?
The line in bold implies they lived there.
