Hi!
I guess you mean the supply stored by the wagons was consumed (that's normal) not that the wagons themselves disappeared (that would be weird)
The supply situation on wilderness areas (most of the map on BOA II) is very hard.
You have to plan how to keep your forces feed. You can add more wagons (the supply will last longer) sent empty wagons back to your depots to replenish and then send them to your armies again, take new supply sources (enemy depots and towns) build depots with your wagons... And of course, don't send more units than you are able to feed!
In any case, there are wild areas where you cannot hope to send regular armies at all. Terrain too difficult, supply too low, distances between towns too big... use fast irregulars (indians, rangers...) there for best effect.
Playing you will come to know the land and find which avenues of approach are suited to send big regular forces and what are not... The map is very big with a lot of regions, but in many of them regulars, guns, wagons and the like are completely out of place. You will see that big armies usually move along some very defined paths, as in history, usually along rivers and lakes or hopping from fort to fort or town to town.
Rivers are great "highways" you can use to move around. Usually is much faster to move armies by bateaux than by foot.
Regards!