From the Super Mario Wiki
The Stork must deliver Baby Mario and Baby Luigi to the home of their mother and father in Super Mario World 2: Yoshi's Island and Yoshi's Island: Super Mario Advance 3. The stork is attacked by Kamek, however, who wants to kidnap the young Brothers before they mature and cause trouble to the Koopas. Kamek succeeds in kidnapping only Baby Luigi and the stork.
After Yoshi defeats Baby Bowser, Baby Luigi and the stork are rescued. The stork then carries the babies to their parents.
In Yoshi's Island DS, the stork is not helping only the Baby Mario Brothers, but also Baby Donkey Kong, Baby Peach, Baby Wario, and Baby Bowser. The stork is more of a major character in this game as it is shown traveling with the babies in cut-scenes, and it helps even more by bringing babies to Stork Stops. In the end, more than one Stork are seen; several storks carry the babies back to their homes.
The first actual mention of the Stork is in The Super Mario Bros. Super Show! episode "Mario of the Apes". When the gorilla couple June and Ward are waiting for a child of their own, they mistake an Albatoss that drops Mario on their porch for the actual stork.
The stork is mentioned in Super Paper Mario about bringing Captain Gills his own children. In Super Smash Bros. Brawl, the Stork makes an appearance as a large sticker that can be obtained. The Sticker shows the Stork carrying Baby Peach. It raises attack power by +21.
The stork serves a similar purpose as his appearance in Super Mario World 2: Yoshi's Island in Yoshi's New Island, as he found out that the parents are not Mario's and Luigi's. While tries to find their real parents, he is attacked by Kamek, and he drops Baby Mario and Baby Luigi. Baby Mario is saved by Yoshi while Baby Luigi is captured by Kamek again. It's also revealed that the Stork and other storks deliver infants from a magic land in the sky.