A fire heated distiller like Ville Niemi's answer is a good idea, but if the fuel and constantly tending the fire aren't practical, you could try a solar distiller. Shouldn't need any space-age materials, just some glass & metal (avoid lead solder!) or wood containers to hold water in.
The Solar Water Still Challenge
The guy in the videos on this page got 3.13 cups of water per day from 3.3 sq.ft of "glass area," or about a cup of water per day per sq.ft of glass.
Actually, if you're worried that glass is a limiting factortoo expensive or scarce, it may not be essential to the design anywayyou can make an old-fashioned solar oven with some shiny metal. A darkThe above design might work with a dirty/dark piece of metal on top, it would get hot and indirectly transfer heat to the water, but probably not as efficiently.
A solar oven would be perfect to put a regular distiller-type pot of water in, with the tube leading out to the "distilled water" container (just like a regular stovetop distiller, but no fuel or fire. Similar to this:
Even a basic box with a shiny interior & lid may be good enough:
Or a more basic "hole in the ground" still (forum link) like this may work too, you may not have access to clear plastic sheets, but a clean dark cloth or tarp may work also (and you don't have to worry about space-age plastic chemicals leeching into the water either).
If there's enough space around people's homes in the city (no high-rises then, but I'm not sure a medieval roof would support a tank of water) they may each be able to have their own solar still & make their own water, no fuel or fires required.