With the Histories being so lengthy, there mustve been volumes of scratch paper and notes he took while interviewing people.
These days journalists have tape and digital recorders and plentiful cheap paper, but with paper being such a luxury back then, how would Herodotus and other authors of the Classical era go about drafting, brainstorming, compiling, editing etc before putting out a finished work?
I can answer in a more general way about ancient historians - others will know more about Herodotus and the scholarship on his work specifically, but there are several things we can learn from later writers that help us to understand the options open to Herodotus and why he might or might not have taken them. One big blind-spot in working with Herodotus is that he's the oldest surviving Greek historian, which means that it's almost impossible to compare him side-by-side with his sources, or to know where he got his information from unless he tells us.
I'll therefore base much of this answer on historians of the Roman period, with a particular focus on Livy, as much work has been done to uncover how he used sources and built a narrative from them. Many of Livy's 'decisions' were in fact largely consequences of the material and technology available to him, and so I'll then suggest a few ways to link his process specifically to Herodotus.^(1)
How Livy Used Sources
Where we can identify a source, he generally follows it closely and exclusively, very rarely directly comparing or intercutting the view from two different accounts. On the other hand, he doesn't tend to follow it for very long - usually alternating between a few favoured sources within the span of a few pages of a modern paperback. While he doesn't transmit everything from his sources, and sometimes adds his own contributions, he does usually take the parts he selects fairly exactly, showing that he was referring directly to their texts rather than a summary or impression. Here, for instance, is the account of one of his sources (the Greek historian Polybius) on Flamininus' proclamation of the liberation of Greece in 196 BC:
While people were still in this state of uncertainty, all the [Greek] world being assembled on the stadium to watch the games, the herald came forward, and having proclaimed silence by the sound of a trumpet, delivered the following proclamation:
"The senate of Rome and Titus Quintus, proconsul and imperator, having conquered King Philip and the Macedonians in war, declare the following peoples free, without garrison, or tribute, in full enjoyment of the laws of their respective countries: namely, Corinthians, Phocians, Locrians, Euboeans, Achaeans of Phiotis, Magnesians, Thessalians, Perrhaebians."
Now as the first words of the proclamation were the signal for a tremendous outburst of clapping, some of the people could not hear it at all, and some wanted to hear it again; but the majority feeling incredulous, and thinking that they heard the words in a kind of dream, so utterly unexpected was it, another impulse induced every one to shout to the herald and trumpeter to come into the middle of the stadium and repeat the words: I suppose because the people wished not only to hear but to see the speaker, in their inability to credit the announcement.
And here's Livy:
But on this occasion it was not the usual attractions alone that drew the people from every part of Greece; they were in a state of keen expectancy, wondering what would be the future position of the country, and what fortune awaited themselves. All sorts of conjectures were formed and openly expressed as to what the Romans would do, but hardly anybody persuaded himself that they would withdraw from Greece altogether*.*
When the spectators had taken their seats, a herald, accompanied by a trumpeter, stepped forward into the middle of the arena, where the Games are usually opened by the customary formalities, and after a blast from the trumpet had produced silence, made the following announcement:
"The Senate of Rome and T. Quinctius, their general, having conquered King Philip and the Macedonians, do now decree and ordain that these states shall be free, shall be released from the payment of tribute, and shall live under their own laws, namely the Corinthians; the Phocians; all the Locrians together with the island of Euboea; the Magnesians; the Thessalians; the Perrhaebians, and the Achaeans of Phthiotis."
This list comprised all those States which had been under the sway of Philip. When the herald had finished his proclamation the feeling of joy was too great for men to take it all in. They hardly ventured to trust their ears, and gazed wonderingly on one another, as though it were an empty dream. Not trusting their ears, they asked those nearest how their own interests were affected, and as everyone was eager not only to hear but also to see the man who had proclaimed their freedom, the herald was recalled and repeated his message.
In parts, Livy's account is almost a translation - I've placed in bold the components which, as I see it, are obvious copy-overs that can't be explained by the content (that is, I've ignored the text of the proclamation itself, where it makes sense for two historians to use near enough the exact same words), and added italics where Livy adds an explanatory gloss - in the first case, reconstructing the audience's state of mind to add to the tension and drama of the scene; in the second, glossing a bit of historical geography for readers who might not have been as familiar as Polybius with the Macedonian sphere of influence.
Oakley notes that there are a quite a few places where we can see that Livy is following a source closely, but doesn't give any explicit hint that he is doing so - which leads him to suggest that much of what looks to be 'original' in Livy is probably based on historical works accessible to him but lost to us.^(2)