Magic.
Again, I dont have a side. There is more than enough evidence to prove Sheik is a male. and Enough that proves Sheik is a female.
And I was wrong, No Japanese Sheik trophy mentions Sheik to be a man. It just never says anything about females. Im not sure if the descriptions says Sheik is male but apparently it never mentions any words that would make you think of a woman.
http://zelda.wikia.com/wiki/Sheik
Scroll down to the Gender section of the page. I think that in Japan, there are more people who believe Sheik is a man than people in America who think Sheik is a woman.
I just don't know.