The king and the nobles usually stayed at the castle or manor of another nobleman they knew.
As many of the barons were related or met one another fairly often, there was usually someone they knew in the district. Many of the lords, and of course the king, had manors all over the country where they could stay.
In the towns there were inns. These were largely for merchants and other travellers who were better off.
