In most cases, they would forage (or pillage) from neighboring areas. As in invading army, they had no qualms about taking whatever they wanted or needed. In situations where they were sending troops considerable distances or for prolonged periods of time, they had to develop other methods.
In some situations they would create relay stations, which would basically be a small camp where supplies could be delivered and then re-distributed to troops further along the supply line. If these stations were in areas where they were subject to attack, then they would be expanded into outposts or forts. In those cases, a contingent of troops would remain to protect the supplies that were stored up, and also possibly as armed escorts for supplies that were being passed along.