I really doubt it's illegal, but most companies have that policy. This country doesn't protect against descrimination based on sexuality, and indeed it seems some states support it.
Anyway, the interview was kind of fun. There were 7 of us, and the guy in charge of the store and the girl who was doing the actual interview talked for a bit, then they left the room, leaving us with the instructions that we were to give each other a mock job interview. So we did that, and then when she came back we introduced and described the person we interviewed. Then she had us go out and pick our favorite toy and then try to sell it to her. I picked the Lego Star Wars X-Wing set.
Then she rambled on about what it's like to work there and what they expect from employes. After her spiel, we went back out into the break room and she called us in individually. I got called in second, and she basically told me that I'd be great and she'd give me a call to come for orientation after the background check goes through.
So woo, I have a job, and the interview wasn't even scary!