Our empire gains +1 influence each month, and need ~50 more. It'll take ~50 months which is a lot of time. So, what can one do to increase the monthly influence of an empire?
Tech. There are several social techs providing +1 influence/month. Additionally one of thsoe provides an empire unique building with +1 / month.
Declare rivalries. You can have three rivalries, together they'll grant 2-3 influence per month.
Complete the mandate. If you play a democratic empire (elections every few years), your elected ruler will declare a mandate (e.g. build 4 mining stations), which will grant a significant influence boost (lump sum of 80-200)
Reduce expenses. Empire Edicts and frontier outposts cost 1 influence per month. There is also tech to reduce this cost.
Some anomalies and events may also grant influence.
Since release the ways of generating influence significantly changed. The wiki provides a comprehensive list. Additionally, the factions in your empire play a major part in generating influence for you.
Addendum to the old points:
Techs are severly reduced. Autonomous agents (for gestalt conciousness) grants +1 influence and living state (for all other races) grants +1 max influence from factions. Interstellar campaigns and galactic campaigns reduce the influence cost of claims. That's all influence related tech left. The empire capital complex building also no longer exists.
Rivalries are still there, but only grant 0.5 influence per rivalry.
Mandates are still in the game, but now grant Unity, not influence.
Empire edicts no longer cost influence per month, but a lump sum to activate for a 10 year period (baseline), outposts are now needed much more frequently than in the release version, they also cost a lump sum of influence based on the distance to your territory and have no influence upkeep.
2As an adjunct to this, are you able to scuttle frontier outposts? I have a few I had to build to increase my borders, but now that I have colonies past them it seems like they are no longer needed.– Ben MSMay 17, 2016 at 0:02
2@BenMS you can scuttle them with the "disband fleet" button, or you can add them to a sector, in which case they also stop costing you influence for upkeep. May 17, 2016 at 4:01
1Holy shit, @PlayerOne, that must be a bug. Otherwise, you could expand your empire a crazy amount, at no continuous cost. O_O May 21, 2016 at 0:41
(Also, of note, enough that you should probably add it to the answer: rivalries scale with both their relative strength (superior, pathetic, whatever), and their distance from you. The best approach seems to be to hunt down a big, powerful empire, but that is across an impassable middle-man, so they have a hard time sending armies at you if they declare war, and make them your rival. Boom, instant ~+3.0 influence/month. May 21, 2016 at 0:43
1@Dpeif This answer is pretty outdated now, as it applies to the Stellaris release version. In the expansions since, the nifluence gain was mostly shifted to the faction system. The only influence related techs left are automonous agents (for gestalt conciousness) and living state (for all other races). The wiki lsits all current sources of influence. I added that to the answer.– DulkanMar 5, 2019 at 7:36
One thing no one else has mentioned is at least in the updated versions you can gain influence by getting factions over 60% happiness
I have found an additional way:
The building "Empire Capital-Complex" that can only be built once provides +1 influence.
But! If you conquer a planet which already has one, it doesn't get destroyed, and you also get +1 influence from it.
So in short; conquer a planet with an "Empire Capital-Complex" on it.
I've found these to mostly occur on capital worlds.
1Sounds like a bug that might get fixed in a future edition. But until then: nice one!– SjoerdMay 19, 2016 at 0:23
If you're running low on influence try removing border stations (or however they're called in english) the ones you use to expand your empire without colonization.