Canals; bah. Slave-drawn wagons; Ho. Hum. What else??
I propose dirigibles.
In 1850, another Frenchmen, Pierre Jullien of Villejuif, demonstrated
a cigar-shaped model airship at the Paris Hippodrome. The airship's
rudder, elevator, and gondola were mounted under the front part of the
balloon. A clockwork motor that drove two airscrews mounted on either
side of a center line propelled the airship. A light wire frame
stiffened by a truss maintained the bag's form. Jullien was onto
something that another man would leverage.
Jules Henri Giffard, a French engineer and inventor, took note of
Jullien's design. He built the first full-size airship — a
cigar-shaped, non-rigid bag that was 143 feet (44 meters) long and had
a capacity of 113,000 cubic feet (3,200 cubic meters). He also built a
small 3-horsepower (2.2-kilowatt) steam engine to power a three-bladed
propeller. The engine weighed 250 pounds (113 kilograms) and needed a
100-pound (45.4 kilograms) boiler to fire it.
Medieval tech can build you an airship. You need a wicker frame (make a few spare Wicker Men this Beltane), and a light envelope that can contain your lifting gas - greased silk would work, or isinglass. Hydrogen is the lightest lift gas, but the molecule is so small it is hard to contain and it requires some alchemy to produce. Helium is good but it occurs only as small percentages in natural gas and must be refined.
But what about natural gas as a lifting gas? Natural gas comes out of the ground in some places. People know it is something different because it can sustain a flame. Methane is light enough to be used as a lifting gas and has the advantages of coming straight from the ground and being a larger and so more easily contained molecule. Plus if you are lucky maybe there is some helium in there as well.
The depicted aerostat has a steam engine. But you could have crew with handcranked propellors, or sails. or giant air oars. Or just go before the wind like a ship with a fixed sail. You would wait for a favorable wind and launch!
Those of you interested in seeing how medieval airships might look are invented to dive down the rabbit hole of google image, from which I have just returned.