I'm not sure they need any special building. At least I know I'm not building one specifically to give overseas cities access. It's possible that the tech for opening up trading overseas hasn't been researched yet in his game. I have 4 cities on a 2nd continent right now with no issues and can trade with civs on all 3 of the continents on the map. Seafaring opens trading across the sea and for trading across the ocean it takes navigation. Those 2 techs could be behind his issue.