The physiology of Toads is not well established, nor was it likely ever meant to be. But when you take the faithful Mushroom Retainers and start throwing in ones with names like "Toadette" that look decidedly more feminine than the original model, we as human beings begin to ask questions. What can we say? We're a race brimming with natural curiosity. And fanfic ideas.
Gamespot recently posed the question of Toads' genders in an interview with Captain Toad: Treasure Tracker producer Koichi Hayashida. The reply might seem a bit odd, and potentially disappointing to anyone hoping a Toad-and-Toadette romance might become canon:
This is maybe a little bit of a strange story, but we never really went out of our way to decide on the sex of these characters, even though they have somewhat gendered appearances. But I think what I can say is that Toadette and Toad are not siblings — perhaps it would be more accurate to say they are adventure pals. And that’s certainly true here.
This may be the measured response of a man terrified of hurtling headfirst into The Birdo Zone, but it must be accepted. Toads don't really have set genders, even if it looks like they do. They're just Toads, and that's enough.
...Or is it? What exactly does it mean to be a Toad? Just what are Toads in and of themselves? Hayashida isn't saying much on that, either:
This particular riddle might stay unsolved. That’s one of the great mysteries of the Mario universe.