The details of how supplies are diminished and replenished are in the "export_descr_character_traits" document in ...bi/ci/data folder. There is an element of chance in almost every change in supply. You can replenish supplies by the act of capturing a city, but less surely, and to less an extent, than by remaining in that same city for a turn; the chance to get supplies in the capturing process might only happen when the enslave or exterminate options are used. AIR both resupply through capture and by remaining in the city are influenced by city size, that is, the level of the government building. I believe you can also reduce supplies lost while in enemy territory (and possibly gain supplies, IDNR) by landing your general on a fertile tile, the more fertile the better; I think only barbarian factions benefit from this option, but nobody can get supplies from wilderness tiles.
If you do not already know, movement penalties incurred via negative supplies are never recovered, regardless of subsequent resupply, so such instances should be avoided wherever possible. I think this is a good reason to remove the movement penalty from the supply trait, if game mechanics allows.