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.
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.