Easily. Initially, cells were haploid. Now, suppose that two haploid cells touched. Just like two soap bubbles, the cell walls could join, and the two cells would become one cell. Suddenly two haploids are one diploid. Just like a haploid sperm joining with a haploid egg. It probably happened a great many times.
Some researchers think that this historical event was connected to the way modern bacteria join temporarily to swap genetic fragments.
Of course, merging is only the start of the story. Next, how would the first diploid survive? The answer is: no problem. As long as the different sets of genetics were similar enough, the cellular machinery would work normally.
Next, how would the first diploid cell reproduce? The answer is: no problem. Asexual reproduction works by duplicating everything. It shouldn't really matter if "everything" was twice as large. The duplication process shouldn't even notice if the cell was haploid or diploid.
Now for the hard one. The diploid cell must eventually learn how to split into two haploids. There's no hurry. After all, a diploid cell can live and can reproduce asexually, so it can become many diploids. But sex involves two haploids merging to be diploid. The new species - the species that likes being diploid - doesn't have sexual reproduction until it produces its own haploids. Only then is there the sexual life cycle: diploid to haploid to diploid again.
The hurdle in the splitting process (meiosis) is that each child haploid must get a complete set of information. The genetic material must be split correctly, and that means that the material has to be kept organized in some way. Modern eukaryotes keep their DNA in chromatin strands. I presume that chromatin preceded the invention of sex. Even early eukaryotes had a lot of genetic material, and some sort of organization would have been useful in itself.
At this point, I can fully answer that Creationist question about how the first sexual creature found a counterpart. When those first two haploids fused to become a diploid, sex had not yet been invented. All that was required was that the two haploids be very closely related, so that their genetics didn't clash. After meiosis was invented, there were haploids of the new sexual species. (And, those haploids could reproduce asexually, forming new haploids.) Whenever any two of those new haploids met, a new-style diploid could happen. So, meeting the right partner was no special problem. Conjugating bacteria had been solving the same problem for years.
To summarize: it was probably all quite straightforward, except for the invention of meiosis. But, as we showed above, there was no critical moment when two inventions had to both happen at once. We know from the fossil evidence that bacteria have been around for at least three and a half billion years. So, there were lots of chances for the first crude version of meiosis to happen.
Genetics and biochemistry are advancing very fast, so the following is probably going to be out of date soon:
The Evolution of Sex, R.E. Michod and B.R. Levin, editors, 1988, Sinauer ISBN 0-87893-459-6
Recent advances in understanding of the evolution and maintenance of sex, L.D. Hurst and J.R. Peck, Trends in Ecology and Evolution Vol. 11 #2 (February 1996) pp. 46-52