From the Super Mario Wiki
Reindeer are a species of deer found on both Earth and Mushroom World. A small team of reindeer are owned by Santa Claus. These select reindeer are capable of flight, and are used by Santa to pull his sleigh across the world every Christmas Eve. Reindeer have made a few appearances on The Super Mario Bros. Super Show!. Both episodes were set during Christmas, and the reindeer in question belonged to Santa.
Reindeer first appeared during "Koopa Klaus", where they, along with everything else at Santa's workshop, had been frozen by Koopa Klaus' Ice Bombs. By the end of the episode, the reindeer were thawed out by the warmth of Toad's Christmas spirit, and were able to help Santa make his Christmas Eve run.
Also worth noting is that in this episode, Tryclyde took on the role of Randolph the Red-Nosed Tryclyde, a spoof of Rudolph the Red-Nosed Reindeer. Koopa Klaus also used two Albatoss to pull his sleigh in lieu of actual reindeer.
The next appearance of reindeer was in "Santa Claus Is Coming to Flatbush". During his arrival in Flatbush, Santa Claus had lost his sleigh, along with his reindeer, prompting him to take refuge at Mario Brothers Plumbing. However, the police eventually found the missing sleigh and informed Santa of the good news. On Christmas morning, Santa and his reindeer rode past Mario Brothers Plumbing to wish Mario and Luigi a Merry Christmas.
In Mario & Sonic at the Olympic Winter Games, two reindeer can be seen pulling Santa Claus' sleigh.