By sex I mean sexual reproduction, the idea that a child gets its genetic material from each of two parents.
Many single-celled creatures use a simpler scheme, asexual reproduction, which basically means that the cell splits into two identical cells. So, the question is, how could the simple scheme evolve into the fancy one? As one Creationist put it,
If an organism mutated into a female who would it mate with??? In order to for it to reproduce it must find a its mutant male counterpart. The odds that an asexual organism would mutate into BOTH male and female and have the ability to reproduce sexually are almost infinite.
Males and females are pretty different in "higher" animals. So I agree that sex could not have evolved among monkeys, or lizards either. Instead, the evidence is that sex was invented long before "higher" creatures came on the scene. Sex was invented just once, perhaps two billion years ago, by a single celled organism. Plants and animals both have sexual reproduction because they both inherited it from their common ancestor. And, at the beginning, there were no "males" and "females". At first, sex was between two single cells that were equals.
To explain, I'll need three technical words. First, a eukaryote is a cell with a nucleus. A eukaryote can be haploid or diploid. Haploid just means that the cell has a single copy of its genetic information. Diploid means that it has two copies, one from each parent. The two copies will be very similar, but are not totally identical. Every cell in your body is diploid, except for sperm or egg cells, which are haploid.
Now we can talk about several things: