As soon as I get the techs needed to stabilish embassies the game asks if I want to have them. So I do it with every other nation I have already found.
Problem starts when I find other nations later on. The game does not ask whether I want to stabilish embassies with them even after I get a trade route set (so that I may be sure we are properly connected), and I don’t know how to do it by myself.