Speaking for the Greco-Roman world: from earlier historians, from observation, from archival records, and to a limited extent from personal travel and investigation via word of mouth.

Most extant historians were synthetic writers, aggregating and repeating the works of earlier historians, sometimes with some half-hearted source criticism. Some of the most valuable ones wrote about things they had personally witnessed or been involved in (Thucydides, Xenophon, Polybios; and Polybios is extremely critical of one historian in the first category, Timaios). Not many extant historians, if any, dealt heavily with state archives, though they certainly existed, and some phrases in Tacitus suggest that he relied on them heavily. A few (Herodotos, Pausanias) made face-to-face enquiries about local oral traditions, with mixed results. And then there are the gossip mongers like Suetonius, Plutarch, and Dion Cassius, who seem to have chewed up any old thing and who can rarely be trusted.

Livy, for example, was mostly a synthesiser of earlier historians like Quintus Claudius Quadrigarius, Polybios, and Valerias Antias. He did have access to official pontifical and state archives too, but he doesn't advertise the fact much; at one point (6.1) he laments that records from before 389 BCE were destroyed in the sack of Rome, though other evidence suggests that some records from before that time survived, and even after that time records were not exactly thick on the ground (in fact the claim seems to be simply a repetition of the opinion of one of his predecessors, Paulus Clodius). How do we know? Because he occasionally cites his sources. He is not systematic about this, and if his writing were marked by a modern history professor he would be failed for his terrible referencing. But his occasional mentions of his sources are enough to get clues as to what kinds of sources he drew on.

A typical citation would look something like this, from Livy 2.40.10-11:

In Fabius [Pictor], by far the most ancient source, I find that [Coriolanus] lived to old age; at least, he reports that he often commented on his advanced age, saying that exile was much harsher for an old man.

We have nearly 30 fragments of Q. Fabius Pictor transmitted via references like this. From such references it's possible to compile the fragments of the lost authors from many different surviving sources, and new editions of these fragments are a very important aspect of scholarship in this area. The ongoing Fragmente der griechischen Historiker and New Jacoby project is the most important accumulation of fragments of lost Greek writers, covering a couple of thousand lost authors; and last year a new edition came out of Fragments of the Roman Historians.