The letter of passage is the sign of a treaty with right of passage worked into it. There are lots of different negotiations you can make now (thank heavens, been waiting for a good diplomacy engine in TW since Shogun).

You can basically barter for Right of Passage by offering to attack someone's enemies, or pay them, or make a trade agreement, etc. Then you can move your armies into their territory without provoking a battle. However, if you have no right of passage, I believe that if you move an army into a "cell" that's occupied by another faction, then there will be a battle... no option to say "just passing through!" on a case-by-case basis.