We do not know for sure, since sexuality evolved too early to be seen in the fossil record, but we can infer quite something from extant species, since they cover the full range from asexuality to sepearate sexes.
Let's look at the animal kingdom (a number of parallels exist in the plant kingdom):
Simple single-celled creatures reproduce by dividing. They occasionally swap genes by a process called zyzygy, where two individuals couple up and exchange genetic material. You could define this as asexual reproduction, although it might also be seen as a form of hermafrodism.
Polyps generally reproduce by budding. They exchange genetic material by several processes, sepending on species, from a zyzygy-like coupling, to a full-fledged sexual connection. They are either hermafrodites or separate sexes.
A number of non-vertebrates (snails, worms), are full-fledged hermafrodites. They mate with another individual, and both produce offspring. Some species are have a seasonal sexual specification, that is, they are males at some times, females at others, some alternating, others going through a life-cycle where they are first one gender, then the other. Insects and aracnids mostly have specific genders.
Finally, moving to the vertebrates, these have nearly invariably separate genders, but there are exceptions. Certain species of fish can change gender at least once in their lifetime, being fully functional as both genders.
If we try to infer the evolution of sexual reproduction from this, it seems to be like this:
Single-celled organism, asexual reproduction. Genetic material exchanged by zyzygy or similar process.
Multi-celled, but primitive organism, specific sexual glands develope, full hermafrodites.
More complex organisms, seasonal or life-cycle dependent sexual specialisation.
Fully separated gender specialisation.
Hans