First, just for fun, here is an article I wrote for Of Sea & Shore magazine on mollusk reproduction that details major aspects of sexual biology and then talks about specific mollusk reproductive strategies (entitled "Behind the green operculum"). Be forewarned, it is not from a peer-reviewed journal and was written to amuse and inform. also, it is by far the worst written piece I have ever submitted (I had less than two weeks two write it from when it was suggested). Check out:
http://www.ofseaandshore.com/greenoperculum.htm.
I think Extremophile's comments are most relevant to this topic. A large number of protists have what are called isogametes. To reiterate, these are gametes that are merely packets of DNA contained in a membrane with varying amounts of supportive cellular contents. In those species that have pure isogamy there is no such thing as male or female. Within the phyla of protists we see all stages of the evolution of sexual reproduction. The most primitive is hologamy. This is where two single celled organisms combine, exchange DNA, then split and then asexually produce clones. This is probably the first eukaryotic "sex". The flaw with it is that genetically both parents are dead. The resultant beings are a mix.
The next step is to meet a conspecific, clone yourself with a minimal amount of cytoplasm and a full complement of DNA and let that 'minimee' comingle with your partner's progeny and resort into two individuals, leaving the parents intact. At this step we have true isogamy. Once we have isogamy then selective factors as mentioned by Extremophile take over and lead to separate sexes as we see them today.
I think it is important to remember that our definition of male and female in a biological sense is only related to gamete size. Mammal sexes are defined by XX and XY chromosomes, but this is not the case in most organisms. Males are those individuals who produce motile gametes that tend to have reduced cytoplasm and associated organelles. Females have large gametes with supportive organelles and a large amount of cytoplasm.
Because of the great diversity of reproductive patterns we see in protists, even within different phyla, I think it is likely that sexual reproduction evolved separately, possibly several times within the existing multicellular kingdoms or their immediate protist ancestors.