Sexual reproduction is extremely valuable within a gene pool because it increases variation which allows for more selection to occur. The end result is that it accelerates the evolutionary process dramatically. And since all (that I know of) of the more complex multicellular organisms on this planet reproduce sexually, it's likely that we only exist because of sexual reproduction.
On the flip side it should be noted that asexual reproduction has not "died out", probably because it has advantages too, namely that it's very convenient and effective. It's probably even more functional in certain environments that sexual reproduction is. Usually for microorganisms.
As for the original evolutionary steps required to bridge the gap from asexuality to sexuality, it's a virtual certainty that the first organisms to share genes in reproduction were neither Male or Female, but simply organisms which each reproduced by combining genes from another organism. At this stage they were probably too rudimentary even to be a combination of Male and Female, but rather they were simply "sharers".