There is a box in the lower right corner of the screen. On the right hand border of that box, there's an "E." Click the E, a screen will pop up with all the civs you know. Click on a civ, click on the build embassy button, and pay your gold. There are other ways, but that's the one I use.