I never knew this was such a big deal until I began my fanlisting for Sheik, and refered to Sheik as a her throughout the site, as I do on this one. I got several comments from people saying Sheik is infact a male, get it right, you silly webmaster, and so I put a disclaimer up saying that I thought of Sheik as female, because she is Zelda, but go on and think whatever you want to think.
The quote that most people use to prove Sheik's masculinity is what Ruto says after Link beats the water temple:
"If you see Sheik, please give him my thanks, OK?
However, in the Nintendo packet that comes with SSBM, the blurb on Sheik is this:
"A mysterious warrior whose moves allow her to flow across battlefields."
So is Nintendo trying to screw us here or what?
The problem is that Sheik is a male disguise for a female character. By becoming Sheik, Zelda seeks to pert attention from herself, and avoid Ganondorf's minions. Her disguise is more effective if people think that she is a male. That's why Ruto refers to Sheik as a him.
The girl dressing up as a boy and running away to do things she couldn't do otherwise is a long-standing literary tradition. My personal favorite example is Portia from The Merchant of Vencie, who dresses up as a lawyer to free Antonio. However, perhaps better suited to my purposes is Viola from Twelfth Night whose disguise is more long-term. As a way of protecting herself, she enters into the service of the Duke:
Conceal me what I am, and be my aid
For such disguise as happily shall become
The form of my intent. I’ll serve this duke.
Dressed as Cesario, the Duke's page, she unwittingly attracts the attentions of the Lady Olivia:
VIOLA That you do think you are not what you are.
OLIVIA If I think so, I think the same of you.
VIOLA Then think you right: I am not what I am.
OLIVIA I would you were as I would have you be!
VIOLA Would it be better, madam, than I am? I wish it might, for now I am your fool.
Viola, however, falls in love with the Duke, and expresses her feelings in the third person (I have this friend...):
She pined in thought,
And with a green and yellow melancholy
She sat like patience on a monument,
Smiling at grief. Was not this love indeed?
Luckily this is a comedy, and all's revealed in the end, with weddings and happiness for all. Still, the point I've been trying to make is this:
If nothing lets to make us happy both
But this my masculine usurp'd attire,
Do not embrace me till each circumstance
Of place, time, fortune, do cohere and jump
That I am Viola: which to confirm,
I'll bring you to a captain in this town,
Where lie my maiden weeds; by whose gentle help
I was preserved to serve this noble count.
Viola remains Viola throughout, despite all the Cesario hijinx. She is aware of herself, a woman, through the play, though she is disguised as a man, thus, it would be proper to refer to Viola as a she, though some people, under the influence of her disguise, have done otherwise.
This argument for femininity only works if you accept that Zelda realizes she is Zelda within the disguise of Sheik. The canon of Ocarina of Time implies it, when Zelda reveals herself, and says "I apologize for meeting you in disguise, but it was necessary to hide from the King of Evil." Indeed, the aura of confidence and the tone of the encounter lead me to believe that Zelda knew what she was doing all along. This is further supported by Zelda being able to transform to Sheik at will in SSBM.
However, the manga version, Zelda no Densetsu, paints a different picture. In this version Sheik's loyalties are very much in question, and we see him speaking with Twinrova and ostensably working for Ganondorf. In this version the implication is that Zelda hid her conscience within Sheik, and that she needed to be awakened, much like Tetra in The Wind Waker. This is again stressed when Zelda states that she can't go back to Sheik again, after Link comments that he'll miss him. By this story, Sheik would more properly be called a male, because whatever Zelda was was hidden deep down within him.
I accept the game version as more strictly canon and therefore continue to refer to Sheik as a her. Really, I think it's a minor detail, as sexuality doesn't ever come into the Zelda games, and anything I say is pretty much conjecture. As I've pointed out, the official evidence is conflicting. The important thing to remember is that Sheik kicks ass no matter what.