Villages are generated objects on the map. Similar to capturing a city, after a unit has moved into a village, the village can be captured the next turn and will turn into a city with its name in the style of the tribe who captured it. It will not change its name if it is conquered by another tribe.
Villages will always spawn at least 2 tiles apart.
A useful tip to note is that natural resources (fruits, game, whales) will only ever spawn within a 5x5 area of a city or village, so you could employ this to find villages when exploring.