If I had to guess, I'd say it's all about eye contact. Where our eyes go says a lot about what's on our minds, and in the same way that one might reflexively turn one's head in the direction of a sudden loud noise, we are not always in control of where our gazes land.
To me, gaydar is all about that searching gaze that's held for a millisecond too long. Perhaps there's something behind that gaze that we are subconsciously aware of, or a slight tweak in our facial expression that, in tandem with the eyes, sends a subtle message. I know I don't look at women, or men who I have absolutely no physical interest in the same way that I would look at someone I would consider attractive.
Our eyes meet the eyes of strangers constantly. It's instinctive. Most of the time, that gaze is quickly broken, and without any thought. But because humans are complex and extremely sexual beings, when we see someone we'd like to have sit on our face, there's probably a whole lot more going on in our brains than there is in those fleeting, meaningless glances we exchange with people who we'd rather not have sit on our face. I'd be willing to bet that an EEG would prove this.
Of course, it would follow that straight people experience the same thing, the difference being that for them, finding a partner is like standing with an empty plate at a smorgasbord, whereas for gay men it's more like a single cheese platter in the corner of the room (with the requisite multi-colored frilled toothpicks and six different kinds of organic lettuces for them to be carefully and painstakingly arranged on. Perhaps some of them are shaped like little penises.)
How kind it was of God to instill in his homosexual children a method in which to connect that significantly reduces our chances of getting punched in the jaw.