How do long rivers exist? I was recently on a long-haul flight over Siberia and it struck me as rather remarkable that something like the Lena River could exist. It seems very surprising that there's a route from some random spot near Lake Baikal over 2,800 miles or so to the Arctic Ocean, which is downhill all the way. Likewise, the Missouri River tells us that there's an even longer downhill-only route from some place in Montana to the Gulf of Mexico.

But these things certainly do exist and it's a pattern repeated all over the world: the great majority of the Earth's surface is drained by rivers that run downhill to the sea. They don't get stuck and they don't seem to form huge numbers of lakes where they have to flood an area to raise the water level over some barrier. I'm aware of endorheic basins, which don't drain to the ocean but they only cover about 18% of the land surface, mostly in central Asia.

Is the existence of long downhill routes more likely than I imagined? (I can't tell if I think it's more likely in mountainous areas than in flatter areas, which suggests I have poor intuition about this) Or is it just a coincidence of our planet? Did the rivers make the downhill paths themselves?
Well, I can only agree that it is indeed amazing and it doesn't get less amazing when some geology, hydrology and geomorphology is added to the the amazement. 

All precipitation that falls on land must flow back to the oceans somehow, and unless it evaporates it will flow in rivers or as groundwater towards a lower hydrostatic level. Water can not flow uphill, so it follows (and crafts) the slope in topography. Water will flow from mountains towards the ocean and due to geometric and morphological reasons, rivers joint to a drainage pattern due to the geology and topography.

Mountain ranges are often formed from orogeny, where tectonic plates collide. Rivers starts at high altitude, radiating out in all directions from mountains, but as collisions in the present continental settings are often on the rim of large plates (e.g Andes, Alps, Himalaya), and the rivers can't cross the range, it will have to travel the whole continental plate to reach ocean level. In the case of Asia, most large rivers starts in Himalaya (or other tectonic active regions, as Altai), in Europe large rivers starts in the Alps. In Africa, they start in the tectonic active rift zone. 

This map shows the ocean drainage dividers. The border between the drainage areas are the line where rivers start. 



Lakes could be understood as temporary stop in the flow, and it will quickly fill up with vegetation and sediments as the velocity of the water decreases. In a geologic context, lakes are never very old, Baikal being the oldest, 25 million years. Drainage patterns are often much older. 

So why are some rivers so long? Because of tectonic uplifts and orogenies. The answer to your question 'Did the rivers make the downhill paths themselves?' is yes, as erosion works toward the peneplain (low relief).