It's not that far, particularly as Heroditus was from modern day Turkey; there are accounts of greek trading posts on the georgian coast on the far eastern side of the black sea.

Boat to the coast and then up river would probably have been the best option for travel.

As for why, why do people generally travel anywhere, particularly writers and historians?

It's very hard to say anything for sure about where Herodotus actually went. The only way we can discover anything about his travels is through exegesis (to draw out information solely from the text) - no other sources about his life exist. Sometimes we can be sure that he went somewhere because his description of the area is too accurate (i.e. Delphi) sometimes not (he messes up the geography of the Athenian acropolis). I'm not sure about the specifics of Moldova however.

To show how difficult it is to say anything of certainty regarding his life and travels there was an idea put forwards by Podlecki in 1977 (Herodotus in Athens) which questioned whether he had ever set foot in the Athens. If memory serves me correct (it has been a long time since I read it) Podlecki concluded that all we can say for sure is that Herodotus sailed past Athens due to his descriptions of the coastline. Any evidence past that is very shaky.

In short be skeptical (to use the term of George Boys Stone - positively skeptical) of all that you read regarding Herodotus' life.

I realize however that doesn't answer your real question as to how he traveled. We know that he was educated (to the extent that he invented history as a genre) and therefore probably had money and he may (or may not) have been in exile after an uprising against the tyrant Lygdamis.