Short answer: they weren't found, they were kept all along -- or rather copied, by people who were on the whole as interested in them in the past as people are today.

For the first part of your question, the best source of information for this kind of question is to check a recent critical edition. The 2015 edition by Nigel Wilson, for the Oxford Classical Texts series, states

There are some sixty medieval and Renaissance manuscripts. None of them is earlier than the tenth century.

and he goes on to describe the manuscripts, which are held in various collections in Europe, and which fall into two manuscript traditions:

• For one branch of the tradition, the main copy is an early 10th century manuscript held at the Biblioteca Medicea Laurenziana in Florence, Italy, catalogued as Plutei 70.3.

• For the other branch, several manuscripts are important: one in the Vatican Apostolic Library, Vaticanus graecus 2369 (10th century), and a group of four manuscripts which go back to a lost ancestor; the surviving four are held at the Vatican and the Österreichische Nationalbibliothek in Vienna.

In total there are seven manuscripts that he draws on regularly for his edition, held in Florence, the Vatican, Cambridge, and Vienna. He cites a few others less frequently, some held in the same libraries, others in Nürnberg and Paris.

Many manuscript collections have put a lot of work into digitising manuscripts, so some of these are available to look at online. The Laurentian manuscript, for example, is here. Vat. gr. 2369 will probably become available online at some point (the Vatican has made more of its collection freely available than most libraries, but it costs a lot of money and it's a long process).

Ancient books were transmitted by an ongoing tradition of copying and re-publishing books. In antiquity this was done by booksellers who got scribes to make new copies; there was a severe decline in book culture in the Greek-speaking parts of the Mediterranean between the 6th and 9th centuries, and when it revived starting in the mid-800s, it was thanks to a mix of secular and ecclesiastical scholarship. Book culture in Constantinople was more or less continuous from then until 1453.

After that point, the text of Herodotus survived in copies that had mostly been previously transported to Italy, and disseminated from there. Manuscripts made in that era -- after the development of the printing press -- are often very important too. In the west, different manuscript collections had different levels of stability and permanence. For example, one collection now held at the Vatican, the Palatine collection, came from a collection that was captured in the Thirty Years War from the Electoral Palatinate in Heidelberg in the 1500s-1600s. This in turn had been swiped from the monastery of Lorsch when the monasteries were dissolved in the 1560s. And Lorsch in turn got its collection from a range of sources.

I wrote a piece last year that gave a bit more context for the story of how Greek literature in general survived to the present day. There are many printed accounts out there too, though for my money they tend to underplay the importance of Greek scribes and scholars in the renaissance.