First and foremost, for an army recommendations and even regulations would be always conditional on availability; if there was not enough cheese available or if cheese had gone bad then simply cheese would not be distributed. In other words, the fact that cheese was recommended does not mean that every time the soldiers had to do long marches they would have been supplied with it.
Second, I think you imagine a marching army that carries with itself all the supplies needed for the march/campaign. More often than not, the army would forage or resupply on the march, through the purchase of food (if in friendly terrain), the use of previously established supply depots1 and by simply plundering whatever they needed (if in enemy territory or if the locals were not willing to provide food)2.
An army trying to march with all of its supplies has lots of complications; not only you need a long supply train that you need to defend and that slows down the army, but you also need to feed the people and the animals of the supply train itself, thus putting an upper limit to its utility.
Obviously, since one of the main functions of these depots was to store foodstuff, they were designed in order to conserve it as best as possible. In "The Logistics of the Roman Army At War", by Jonathan Roth, it is stated (p.185):
The ancients had the technology to store grain for as long as ten
years. The Romans understood that in order to preserve grain
for the longest possible period, the temperature and moisture content
of the grain had to be kept as low as possible
And, while cereals were the main aliment for the soldiers, such depots contained other items (p.187):
A granary or horreum did not only store grain: the low temperature
and ventilation in granaries helped to preserve fresh and salted
meat, cheese, lard, vegetables, olive oil and wine. Frontinus refers
to the “food supplies” (alimenta) stored in the horrea of the Roman
army after the battle of Teutoburgerwald in 9 A.D.230 Several horrea,
such as those at Balbuildy and Ilkley in Britain, have revealed
amphora fragments. The author of the African War refers to a camp
storing, in addition to grain, wine, and oil, “other necessary items
which had been gathered as provisions.”
Additionally, when available, carrying supplies by ship (either through the sea or through rivers) allowed them to be transported faster.
And let's not forget that it was not only the army that didn't have access to fridges. Conservation of the food was an important issue to everybody, so long lasting varieties would be preferred for storage. You would get to eat fresh cheese (or meat) only shortly after it was prepared; everything else would be elaborated/salted/smoked so it could last as long as possible.
This option was more used by well organized states like the Roman Empire; medieval logistics were far more "medieval".
2In page 200 of Jonathan Roth's book, "The Logistics of the Roman Army At War", we find an upper bound for how far an army could go from its supply base:
In practice, the Romans did supply armies overland for well over
100 km. (60 miles)—and occasionally up to 320 km. (200 miles). There
are a number of examples of this attested in the sources.