This is from the top of my head, let me know if you want more specific information.
First of all, bacteria participate in the swapping of DNA, so even the most simplest of life forms is capable of what we would call "reproduction". However, with bacteria this is usually limited to small bits of DNA instead of half the genome, as is seen in mammals for instance. Also, bacteria absorb extraneous DNA from their environment as well, and can incorporate this DNA into their chromosomes. This is called "horizontal gene transfer". The production of gametes (eggs and sperm) may have been a evolved pathway towards more specific DNA transfers, that is keeping DNA isolated to the same species instead of casting DNA "to the wind" so to speak.
Secondly, we also see that many species are not strictly separated into male and female. Take earthworms for example, they produce both sperm and eggs, and fertilize each other during mating. Once the apparatus is there, it wouldn't be too difficult for the sexes to be separated permanently.
So, with species alive today we see a gradation between simple DNA swapping---> gamete swapping ----> sexually separate species. There are probably many intermediate steps between these three, but the pathway seems to be well evidenced.