i don't understand influence. it feels like a pointless mechanic that doesn't serve much purpose. It's a pretty broken and sparsely implemented mechanic, and seems like worthless bloat considering the number of resources we already have. i've rarely felt satisfied with getting more influence, and rarely have any use for it except to sell it to the AI (who has no use for it either, judging from the amount they seem to stockpile.)
The primary way of getting it is to find "Prestigious Location" in the strategic map. They look like a big flat-topped rock. They're considered a natural resource, and you can build a "Monument" on top of them, which provides +1 influence to your empire per turn. There is also a town level which gives +1 influence per turn as it's bonus, if you choose that, it's called Embassy i believe. Aside from that, it is possible for certain rare quests to give you influence as a reward.
The tooltips hint that influence is used for hiring "wild" units. wildlings, bandits, ogres, trolls, those strange knights, and presumably dragons. Personally i've never found a use for any of these things, as the first five are worthless and weak, and dragons come too late in the game to be useful.
Aside from that, certain empires use influence to build their unique units. Resoln can use 100 influence to build the sion unit, which seems to be broken (according to the tooltip i'm supposed to be able to give them equipment, but that isn't true) and thus worthless. The altarians can use 50 influence each to build a henchman unit, which are pretty darned good. perhaps there's more, that's all i know of at the moment.
In my experience, the AI seems to consistently buy influence from you at a value of 2 per influence point. They'll also sell it to you at the ridiculously broken value of 100 (!) per influence point. You'd have to be stupid to buy that. But as far as selling it to them goes, it seems like money for old rope to me.
Personally, i don't see much reason or value for influence, at all. I wouldn't miss it if the mechanic simply vanished entirely from the game. i don't see what purpose it fulfills at all.