Indeed, trading maps will give you the bonus. I'm not sure exactly how it works - but I think that player number one, if trading with, say, player number six (who has a nearly full map - or completely full when combined with player one's) will always be the one to be given the bonus. In other words, the player higher up on the playing list might always be the one to get the bonus during such a trade... It's only theory, and probably not correct.
Also, certain AI seem to like to explore much more than others. I have noticed that Washington will quite often send a few boats out in either direction as soon as possible in order to circle the globe - so be sure to do some map trades with him. I'm sure there are other leaders who like to navigate the globe as a priority, as well, but none come to mind.