I'm afraid I can't comment much on Thucydides and Sima Qian, but I'm quite a fan of Herodotus so I'll say a bit about him.

Herodotus got most of his information from people he talked to. He was quite well-travelled himself (he claims to have visited Egypt and talked to the priests there - though some historians think he might be lying about that) and seems to have collected most of his stories from other travellers and seafarers that he encountered along the way.

His other major source was the Temple of Delphi. It was quite common for cities and rulers to send gifts to the temple, either as an offering that came with a visit to the Oracle, or as thanks to the gods for a victory. These might take the form of a statue, or some sort of gilded treasure like a bowl or candelabra. Many of Herodotus' stories are linked to one of these items and how it got there. One gets the impression that he spent a great deal of time there picking the brains of whoever was responsible for looking after them, a bit like an overenthusiastic tourist interrogating a museum curator.

The thing I love about Herodotus is that he is extremely open-minded. He writes down anything and everything he hears. There are a few points where he says "I don't believe this, but I will include it anyway just in case...". This is how he ends up with some extremely outlandish and entertaining stories about giant ants guarding piles of gold in the middle of far-flung deserts, but also means that when he hears several conflicting narratives, he reports both. Other ancient historians (I understand Thucydides has a particularly bad reputation for this) tended to decide which version of events they believed and then report only that, so that other narratives are lost to history.

Sources: Herodotus "Histories".