Sex (physical characteristic): While a great majority of people are clearly male or clearly female on this measure, there are some who aren't (see "Sex/gender"). This measure isn't necessarily extensible to non-human people either (space aliens, intelligent robots, deliberate mutants, levels of emergent behavior that exist at greater/lesser scale than humans, etc.)
Gender (what gender do you identify with): Not everyone identifies with a gender, even if they have a clear sex. Me in particular, who has sex "male" but generally dislikes identifying with categories, and in particular, neither being wholly male nor female seems to suit me. Judging oneself in every detail, by a category chosen because of general fit, seems indirect and not right: just try to use the original, innate judgment without channeling it through a known stereotype. Placing oneself in a category, or in a mentally binding agreement, creates false stability... If I had to and was (easily) able to choose, I would probably choose female... but I don't have to, and it's not trivially easy to choose to be a gender different from one's sex semi-officially.
Sex/gender (are you male or female): Often a somewhat-arbitrary decision is then made about a new person, for the social/political reason of everyone having the "female" or "male" gender. If this belief is true, then (helped by the informal collaboration of behavior according to the gender stereotype, and the habit of covering up our own and each other's bodies with clothes and shame) we think more people are a clear sex than actually are. Bathrooms in the country where I live are often labelled sex/gender-specifically; while they may have some specializations for the sex, much of their functionality works perfectly fine for just about anyone. Effects from parents, peers and others tend to make one's knowledge more limited than it ought to be; a poor example being skirt-shopping skill. Governments, surveys, standardized tests, and all sorts of applications, appear to require one to be "male" or "female" and tell them which.
Informally, the English language wants to choose "he" or "she"; there are workarounds like "they", the person's name, inventing new pronouns, and not worrying about which pronoun you use (I like the latter - diluting meanings - but like the other methods, it can be quite hard).
Much of the above goes for sexual orientations (and races?), except that categorized sexual orientations aren't nearly as mandatory around here as "male"/"female" sexes are.
