How do I establish embassies?

[Bosh]

The only ones I get are from the screen that pops up when I get writing

[ixnay]

Click the star under your capital that indicates it is your capital. Later on, that is where you plant spies, too.

[Dugrik]

Alternatively, you can right-click on your capital and select "Conduct Espionage". After Writing it'll allow you to set up embassies, after Espionage it'll give espionage options as well.