You gain Influence by getting certain retinues (such as a decorated veteran). There isn't really a set way to improve influence like you do other skills. Command increases from fighting and management increases from being in settlements with Academies. You get influence by winning major battles and just being "influential." Other than that, you can get the character to gain an important Senatorial position (such as Consul). This will bring 5 influence (I think).