You need to linear interpolate from non-fogged to fogged. Either use some dynamic drawing or pre-defined tiles. If you use predefined tiles you will have the following setup:

701
6X2
543

The X is the currently drawn tile and 0..7 are the neighbor tiles. If X is fogged, the gradient is defined by the fog-state of the neighbor tiles. As you can see, you just need to check the tiles and combine them in a byte, something like this:

if(isFogged(x,y) {
  int fog_tile_overlay_index =
    isFogged(x,y+1) << 0 |
    isFogged(x+1,y+1) << 1 |
    isFogged(x+1,y+0) << 2 |
...
    isFogged(x-1,y+1) << 7 ;

  tile fog_tile = getTileByIndex(fog_tile_overlay_index);
}

Advanced:

To reduce the number of tiles, you can utilize symmetries by mirroring or rotating the tiles on the fly.

an alternative is to render those black tiles into a white surface and put a gaussian blur on it, then multiply the full rendered tiled screen with the blurred surface. as a gimmick, instead of having just fully fogged or non-fogged tiles, you could actually use values inbetween, either by distance to that tile or time based once a tile is uncovered.

if you draw in software, that fog can be calculated in a one channel texture and gaussian blur is separable, with two passes it's fast enough for most cpus.

You might also want to reconsider your fog as shadows, and implement a lighting system instead, since the example you provided uses the "fog of war" as sort of shadows.

the first screenshot looks like simple range based lighting, the further it's away, the less bright it is. there are various ways to implement it, simplest is probably to just multiply some texture over the screen that has the circle with falloff.

2nd looks like 2d lighting with shadowmapping, applied on top of the 3d rendering to simulate the player's view. there is a neat article bout it here on gamedev:

http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/page3.html