While the tale I'm going to tell you is certainly not anything new, it's interesting enough to be brought up now and again for the benefit of those not 'in the know': Birdo started "her" life out as a video game character a bit differently than you know "her" now.
Namely, popular belief has it that Birdo is the first transgendered video game character (there's obviously no official comment from Nintendo on this.) Why? How!? Well, let's flip through his past, through the pages of old instruction manuals and game art.
His first appearance was made in the US/UK release of Super Mario Bros. 2. He was found as an end level 'boss' and fired eggs out of his mouth. Here is his description as found in the instruction book
Note: The book swapped Birdo's and Ostro's names in the manual, Ostro is actually the ostrich that Shy Guys are often found riding. However, the description is obviously still meant for Birdo.
So during the adventures of SMB2, Birdo was most definitely a he. Birdo simply aspired for a different lifestyle.
Let's advance through time.... to Mario Tennis, Birdo's first chance to reappear in a Nintendo game.
Well, she kept her name, but she changed other things! Namely, he's now officially a she! Also, now that she is a woman, she also get's the steortypical 'agility' attribute.
But let's not stop there. Birdo, now comfortable with her life, has decided to seek love.
You think Yoshi is aware of Birdo's past?