I don't remember exactly how it came up, but somehow last night we got to musing about the origins of words like sex and gender with Porteiro and Beverly. I told them I'd look into them, so here we go.
Sex comes from the Latin sexus and meant much the same thing then—the state of being male or female. It probably comes from secare, meaning "to divide" (because sex divides the world into male and female). But as a shorthand for "sexual intercourse," it only dates back to the early 1900s.
Gender comes from the same root as genus and meant "kind, sort, or sex." This ultimately traces back to a Proto-Indo-European root meaning "to beget, to produce, to be born." Some related words are kin, kind, genius, general, generic, gentle, along with many others.
Originally gender referred to the grammatical category or to genera (the word genus was borrowed into English a couple hundred years later). It wasn't until sex came to mean "sexual intercourse" that gender became a popular euphemism for sex.