As to the assertion that sexual reproduction could not have come about through evolution, Howard Hershey has the following to say about the evolution of sex (he warns that he is stating all of this from memory, but  believes it is a simple task to check his statements in any genetics or developmental biology textbook):

Recombination (a key element of meiosis that differs from mitosis significantly enough to warrant new activities) also occurs in bacteria (which don't have sex as we eucaryotes know it). The bacterial enzymes involved are called the RecA, RecB enzymes. These are enzymes that are also involved in DNA repair. he RecA enzyme in particular is involved in repair of UV damage. Almost any molecular biology or genetics book will talk about the Rec system. Recombination in eucaryotes is very similar but the enzymes are not as well studied. But topoisomerases (enzymes that break and reseal DNA) are clearly involved and these enzymes have a long evolutionary history.

But the key thing to remember is that sex (in the biological sense) is simply the passage from the diploid (2N) state to the haploid (1N) state and back again by fusion. Undoubtedly what these creationists mean is "How can we create two sexes that are so different from one another?" An interesting question when posed by a three-year old but one that ignores the fact that some creatures have an even more dramatic differentiation between the sexes than humans do and some have much less.

The passage of the sexual cycle does NOT require two highly differentiated sexes producing specialized gamete cells. Yeast, for example, are sexual animals just as much as humans and it is hard to distinguish haploid cells from diploid and the difference between the mating types (when the haploid gametic cells are visually indistinguishable from each other they are called mating types; when one is differentiated to hold most of the cytoplasm it is an egg and the other less endowed cell is a sperm with males being sperm carriers and females being egg carriers). There [are] all kinds of variations in nature between the yeast and mammals (although fish carry sexual dimorphism to an extreme unseen in mammals).

Even within humans, sex is not a case of being different from the moment of conception. The early human embryo (XY male or XX female) is sexually dimorphic (has both embryonic male and female parts). Normally a single gene (on the Y) sets in motion a cascade of events that leads to the emphasis of the male internal parts (Wolfian ducts) and degeneration of the female parts (Mullerian tract). Absent that gene, the male parts degenerate and a female develops. Most of what we call male and female traits are purely hormonally caused and depending on the hormonal environment you can get interesting events. I have a lovely picture of a busty young woman who is XY (she has a defect that makes her cells unable to respond to androgens). Internally, she is sterile because the genes that determine the degradation of the Mullerian tract are different. She also has no pubic hair (because that requires a cellular response to androgens). There are also XX individuals with various levels of penis and (empty) scrotum formation because of in utero exposure to androgens (the mothers had a tumor or took certain steroidal drugs). The external genitalia equivalents are very simple scrotum = labia and penis = clitoris. There are all kinds of intermediate situations since this is a question of different differentiation of organs rather than de novo creation of different organs. All this (and much more) can be found in most textbooks of development or genetics. But, amazingly, most creationists seem completely ignorant of these basic facts and somehow think that male and female were created separately.
          (Hershey, 1996) 1