If you go back long enough, the soldier probably slept on hay, hence the older expression to hit the hay. An army on the move would have had many horses and hence much hay.
With more refinement, the hay was contained within a palliasse, a large bag made out of sacking. So hit the hay became hit the sack.
In BE, soldiers are in the army. The navy has sailors.