To trade with another faction you need an unbroken line of ships(at least one ship per sea area) from your port with the trade goods to another faction's sea coast province that also must have a port. There are no land based trade routes between factions. Any landlocked province with a tradeable commodity, only generates trade within it's own province (not a very lucrative amount unfortunately).