Here is a quote from
Message 4.
crashfrog writes:
asexual organisms -> asexual organisms with a mechanism for gene transfer (the vast majority of today's unicellular life) -> asexual organisms that require gene transfer to reproduce (sexual now, but hermaphroditic) -> sexual hermaphrodites, now evolved to multicellularity, where the offspring gestates internally, incurring a biological cost of resources and vulnerability -> sexual hermaphrodites with a biological mechanism to determine which gets to gestate the offfspring -> sexual hermaphrodites where some individuals have phenotypical structures to aid internal gestation -> sexual, sexed organisms where one organism is fated, congenially, to bear offspring and the other to provide necessary genetic material.
A different story altogether, not requiring the sudden emergence of opposite genders that happen to meet.
Message 6 expands on crash's post, if you want a little more detail. Read on some more to get some more interesting tidbits.