Any time your influence border expands (whether due to city growth, city improvements, new outposts, or High Tower outpost upgrades), there is a chance that new land will become fertile, as long as it is a tile-type that will support cities (so no fertile deserts, swamps, or mountains). In order to see this happen, though, the tile(s) must be at least the minimum distance from all other cities on the map.
Additionally, there is a spell available through research in the magic tree (Bloom of Twilight for Empires, Birth of Summer for Kingdoms) gives a chance of creating a settle-able tile on the target location. It won't always work, though.
