This wasn't as big a problem as you might think; it's only recently that modern people have taken the view that life is impossible unless every little detail gets written down.
There was one point, however, where the Greeks needed to do better, and that was recording who owned what land. Believe it or not, there was no registry of land ownership. This made for an interesting problem.
They solved the problem by putting boundary stones around everyone's property. Horos means limit, or boundary. A horos stone is a boundary marker with a legal enforceable meaning. The stones were normally quite large, I suspect they were typically painted white to make them easy to see. Most, but not all, had something written on them: a standard formula declaring the stone to be a legal boundary.
All land, to be legally owned, had to be enclosed by horos stones placed at regular intervals. I think the usual interval was probably a stade, that being the length of the Olympic competition field, and the origin of our word stadium.
Here, from the excellent stoa.org, is one of the surviving horos stones for the agora in Athens. There's an inscription on it that reads, "I am the boundary of the agora." (Horos stones always spoke in first person.)
Needless to say, there were countless court cases where one farmer claimed his neighbour had moved the boundary stones. In those cases it all hung on witnesses. Since the stones were embedded in the ground, moving them would leave fairly obvious holes, even if the culprit filled them with fresh dirt. Also everyone in the area would know everyone else's business and if the boundary shifted locals would probably spot it.
If you wanted to sell land, then the law varied wildly from city to city. In Athens — I'm on shaky ground here, but I think I have it right — both parties had to post the sale with one of the city magistrates for 60 days, after which it was a done deal as long as no one objected. This rule was presumably to ensure no scammer sold someone else's property. There was actually no other defense. I can only assume a few con artists got away with it.