Actually in the present case it is a bit more complicated. If I recall correctly in that particular map you already rule two cities, and you just have to conquer a third one in the way as described by Gweilo, by attacking them with your soldiers. You can also send along a hero and you can ask soldiers from other cities to help you, provided they are friendly enough (in which case they are listed on the popup).
Once you have conquered a city, you have to keep them friendly, otherwise they might rebel against you. Rebellions can be quenced by a conquest, but you may also try to pamper the city with gifts, and in the end they might decide to end the rebellion peacefully.
So just conquering a city is not enough, you have to keep them happy, eg by donating something they really need.