Papyrus or parchment. We now know, thanks to Wadi al-Jarf, that papyrus was being used in Egypt as early as the reign of Khufu (c.2550). By the time of Eratosthenes in the 3rd century BCE, it was common (but not cheap) and reasonably easy to acquire anywhere in the Mediterranean. Parchment was another alternative, and the Hellenistic kingdom of Pergamon (in western Anatolia) was famous for its production. There is a legend that the Ptolemy dynasty in Egypt monopolized papyrus use and did not allow their Hellenistic rivals elsewhere to use it. This is not generally considered to be true, however.

Wax tablets were a cheap alternative for non-permanent record-keeping, though I do not know how much they were used in the Hellenistic world. They were common in the Roman world. Lead sheets were also used as a form of paper, again because they were cheap, but they were difficult to inscribe and hard to read. We find them a lot in use as cheap personal letters and as a medium for curses.