Yoshis were first introduced in Super Mario World. In that game, they are residents of Dinosaur Land - specifically, they live on Yoshi's Island, a part of Dinosaur Land (apparently the species is named after the island). Mario and Luigi are on holiday there after the events of Super Mario Brothers 3, when they find a strange egg, which hatches into Yoshi. He explains that the Koopas had sealed him and his friends into these giant eggs, and Mario and Luigi agree to travel with him to rescue his friends (and hunt for Princess Toadstool, who has been kidnapped). They are not Mushroom Kingdom citizens, then, as they live in their own separate land; but they are certainly more than animals (they can talk, build houses, etc.).
After saving the Mushroom Kingdom from Bowser and the rest of the Koopas in Super Mario 3, Mario and Luigi needed to recuperate from their adventures. Together they agreed that the best place to vacation was a magical place called Dinosaur Land.
But while Mario and Luigi reclined on the beach for a relaxing nap, Princess Toadstool disappeared, apparently seized by evil forces. After searching for hours for their missing friend, Mario and Luigi came upon an enormous egg in the forest.
Suddenly the egg hatched, and out popped a young dinosaur named YOSHI, who proceeded to tell Mario and Luigi a sad tale of how his dinosaur pals were sealed in similar eggs by a group of monstrous turtles.
"Monstrous turtles!," exclaimed Luigi. Bowser and his bunch have returned!" Mario slowly nodded his head in agreement and, along with Luigi and Yoshi, set off across Dinosaur Land to find the Princess ad to free Yoshi's friends. As they began their journey, Yoshi handed Mario a beautiful cape. "This may help you," Yoshi said. "Some say it has magical powers."
With a little luck (and help from a magic cape), our hearty crew can defeat the sever worlds of Bowser's Krazy Koopa Kritters. Many locations are well-hidden so explore everywhere and try everything. Not all locations have to be explored to rescue the dinosaurs and save Princess toadstool, but there are many "starry" treasures to be found in far-reaching places. You'll need to search all areas to find out what kinds of treasures are there... in Super Mario World.