Hi!
the influence adding building starts off as an embassy (and goes through various incarnations as you get tech). It is indeed best to build them on the +100% squares, and they have an effect only on the influence of the planet it is built on. but actually, you'll probably find influence starbases more useful than embassies.
there is also a galactic acheivement, the restaurant of eternity (i forget which tech you need), this has an empire-wide effect, and there is no advantage building this on a +100% tile. tis very useful if you're planning an influence victory.
remember also a planets influence largely based on population and PQ, so not much point building embassies on puny planets.
other tips - research the influnce and diplomacy branches of the tech tree heavily, and build maxed out influence starbases near enemy worlds you want to try to flip. Be ready for the AI to declare war on you if you dont keep a decent military (and possibly even if you do), because they wont like seeing all those influence bases!
grab and protect at any cost any influence resources you can find.
well, cant think of anything else at the mo - good luck