I wouldn't like a some sort of new unit type you'd have to move around. That'd be way too much micro. Some sort of abstracted supply line system would be great, though. Maybe it could work a bit like trade routes. If the enemy manages to "blockade" your army, you'll be in trouble.
When they don't get supplied, they can't heal and start taking self-damage. That's the simplest model, I think. The supply could also affect maintenance costs. An garrison unit within own borders should be base cost. An unit that has fought last round should be +1x. Unit in enemy territory should be 2x. If the supply line to a land unit has to cross water, it's 4x. If the supplies must be dropped from air, its 10x. Not sure of the exact multipliers, but you get the idea. Maybe the player could voluntarily cut supply off for an unit if it was too expensive.
Pillaging should have an effect too. If an unit pillages an improvement, it'll have the "self supplied" bonus state for a round or two. Better results with towns and villages than with other improvements.
if anyone has played Rise of nations, they have an awesome system of attrition to unsupplied units in enemy territory. attrition would decrease health of the unit every second it's in enemy territory. Attrition could be increased and decreased depending on tech and you'd have to have supply wagons in the radius in order to gain immunity from attrition. Also, siege weapons fired 2X as fast if supplied. Also, this idea makes it necessary for players to be organized and goal-orientated in their attacks (also bc of pop limit) unlike in cIV where you can just hurl a billion units at the enemy and hope for the best.
The need for supply wagons creates more defensive opportunity for the defender if the aggressor is not guarding their SW's well enough. Think Nap and Hitler invading russia.