I'm fairly sure that initially trade is only done between cities with a port that you own (that are in close proximity). A trade agreement with another faction means you can trade with ports that they own. Note that each level or port affects how much trade fleets you can have per province, I think the max is three (which is good, no more MTW style trading with every port on the map).