In Heroes of Might & Magic 2 and 3, the terrain system works pretty simply. Each tile has just a terrain type attribute; all those fancy edges are actually picked at run-time, and stored only in memory only while on-screen, and re-picked when they come on-screen. It's not an expensive operation, but it does take more work than would make doing it at render-time acceptable.

All they do is decide the fringe based on the adjacent terrains. And there are a half-ton of restrictions that make it work in a limited art set.

No tile can have no adjacent tiles of the same terrain type. The minimum adjacency is one vertically adjacent and one horizontally adjacent. No 1xX paths, no 1x1 spots. This way, we chop out a huge number of possible fringings.

And to prevent fringing from every terrain type to every other... have you noticed that water always borders on sand? Fire up the editor and turn on the grid. Water tiles border only on sand. Sand borders on anything, and dirt borders on anything. But snow will border on sand or dirt, but nothing else.

So if some map-maker puts snow next to jungle; on the snow tile, fringe from snow to dirt, and on the jungle tile, fringe from jungle to dirt. Try it out; you'll notice that rock wall (Heroes 3) borders only on sand, and then the 'subterranean' borders on sand.

Yes; the graphics aren't generated at run-time, but which fringe graphic (the outer 8 in that tileset you posted) to use at a given tile is chosen at run-time, to save memory.

Doing as the above posters suggest is the way I did it with Golem and with the Accidental Engine. After the map is loaded into memory (or randomly generated, as is the case with my work) a post-processing pass iterates over the map and for each tile it counts the neighbors of the tile that share the same basic landscape type, generating a unique code for a given neighbor pattern and using this code to index into a table of transition tiles. Unlike previous posters suggested, I did not place any artificial constraints on base type placement (isolated 1x1 blocks of terrain were allowed) thus necessitating a larger set of transition types. (46, to be precise). I highly recommend setting limitations, since a 46-type tile set can quickly get out of hand if you want to provide randomized alternatives for each of the transition patterns, to eliminate some of the more obvious repetition.