There are many different ways to do this depending on the available technology, cost and the ground conditions. For example we know the ancient Romans had pile drivers on barges which they could use to drive long piles into the river floor that would support the bridge. Some rivers would also dry up for some parts of the year, at least enough to build a bridge. Or the rivers could be partially drained for the construction. But even with these different techniques available the most common was still ferries at river crossings. Bridges are relatively new most places, most of them less then a century old.