Below is an exact scale reconstruction of level 1 of the fortress in broad daylight in a superflat world. It is now much easier to study how fortresses are auto-generated. A lot can be learned just from this one picture, as we'll soon get into.
After some study, you can see that most of this interior level of the fortress is actually made up of these four 5x5 "building blocks":
This allows corridors to neatly be stacked next to each other (usually), and long corridors are always multiples of 5.
To make things more interesting, sometimes these special building blocks are used:
NOTE: The lava well room doesn't appear until level 3, but I'm including it with the other interior room building blocks above.
Aside from the stairs, the rooms don't fit the standard 5x5 pattern, resulting in more interesting arrangements, such as the corridor east of the balcony that abruptly stops when it no longer fits next to the corridor east of it (yellow stripe).
Speaking of corridor endings, the red stripes indicate a standard ending, which is an exterior (non-roofed) section with strips of nether brick extending out a random number of meters. This is a "broken bridge" section, like this:
Interestingly, in this particular fortress, almost all of the "broken bridge" endings are in solid netherrack, with an air space NOT auto-cleared above the nether brick, so it's a de facto netherrack wall dead end:
Note, however, that if you mine out some of the netherrack, you will still find the "broken bridge" nether brick pieces.
What I marked with a purple stripe I've now decided is just another "broken bridge" ending... except that it ends at a solid nether brick wall (a created solid foundation from a level 3 corridor). It is also open to the air, so it kind of functions as an open-air balcony.
Let's proceed to Level 2.
Level 2 is made up of the same basic building blocks. Note that the nether wart garden room has a staircase that leads to an exterior balcony. The balcony sometimes connects to other interior hallways and sometimes not. The Level 1 garden room has a balcony only so I've not shown it in Level 2. However, the Level 2 garden room above DOES connect to additional hallways, so it's included in Level 3 below:
Before we go further, there is one interesting thing to note. A standard staircase goes up 7 meters whereas a nether wart garden room staircase goes up 8. So technically the garden room's connection is 1 meter above the rest of level 3! This can be shown in the following screenshot where a shortcut was mined through netherrack from the long "exterior" hallway straight up to the interior hallway (approximately 7 meters to the east of the pig in the Level 3 map):
The "exterior" hallways are marked with red brick instead of nether brick in the map. The wall is only 1 meter high with no ceiling instead of 4 meters high with ceiling. Now, if the fortress is generated inside of netherrack as shown in the screenshot above, an airspace is created above the exterior hallway making it like an interior section, but we'll still call it "exterior" in our analysis. (Interestingly, in this particular fortress, ALL the exterior hallways are in netherrack, and only a few interior sections ever reach open air.)
Each nether fortress contains exactly one lava well room which is the gateway between exterior and interior sections.
The exterior hallways are made up of these "building block" units:
Unlike the interior, these are mostly different sizes, but it doesn't matter because the exterior is mostly long corridors on pillars and the corridors are not expected to be placed directly next to each other.
Exterior section staircases are semi-hidden in dark 7x7 "tower" rooms. Interestingly, instead of 8 or 7 steps, there are only 6 (5 block steps, plus one more step up to the tower balcony). Once at the top you always go off in a different direction. Here are the final two levels:
On level 4, I've marked the location of some level 3 walls in green because I wanted to dig at a dead end to examine level 4 foundations. Here's an example exterior dead end which I've partially mined some netherrack out of to expose the "broken bridge" (discussed earlier):
On level 5, it's interesting that the two balconies are next to each other. The first balcony is supposed to connect right but hits a "dead end" at the other balcony. But there is still a space for the connection, though, and it's also a simple process to mine a block to make a way through. The long corridor pretty much leads to "nowhere" but the end of the hallway marks the far end of the fortress and would be a good place to build a nether portal or start mining a tunnel to try to find open space.
Note: The exterior section USUALLY is on levels at or above the interior section. However, I found a fortress recently in which an interior staircase took the interior one level above the lava well room... and also above much of the exterior section. Presumably the exterior normallly generates before the interior, so what happened is that the foundations for the interior hallways landed on the exterior hallways and blocked off some sections... even to the extent of embedding a blaze spawner inside solid nether brick! (There's always new surprises in Minecraft.)
How can I get to this particular fortress?
This page was meant to map a "typical" nether fortress. Obviously, each one will be different, but will be made of the same basic elements. With that knowledge, you can recognize these elements more quickly in the dim light and have more confidence wandering through the fortresses. (For example, you now know to check for a passageway behind the staircase of a nether wart garden.)
However, since this particular nether fortress is near the spawn point, has lots of loot, and is completely mapped, you may want to visit/raid this fotress yourself. Here's how to get to it.
I started out innocently enough by challenging myself to "Ultimate Survival II" (Seed 1283) - three islands in the middle of the ocean with no mainland in sight and just one tree. I planted seedlings, dug a mine, found a cave, found some diamonds, made a diamond pickaxe, harvested obsidian, and constructed a nether portal. When I entered the nether, SURPRISE, I was in the lower-left corner of Level 1 deep in the fortress. How awesome is that!
After further analysis, I discovered that the fortress is in a section of the nether that is almost solid netherrack from top to bottom. This means that the fortress is extremely well hidden and almost impossible to find if not teleported into. The only air cavities seem to be the passages of the fortress itself and a small cavern in the nether ceiling. When I tried re-creating the world and re-building the nether portal on various locations on the main island, I kept ending up in the nether ceiling! And, aside from dangerously digging straight down a LONG way, there's almost no way to find the fortress.
Even though this is not mentioned in the online wikis, apparently the nether portal is sensitive to elevation. When I built the portal above sea level (62), this is correspondingly closer to the nether ceiling cave, so I kept ending up there. Only by digging down a ways was I closer to the fortress passageways and thus ended up there. The lesson? Creating nether portals deep in the earth is a better way to find nether fortresses than creating them high up then having to descend to attempt to find fortresses.
Anyway, the above screenshot shows the EXACT location of my original portal, which I tested and works to teleport me to my exact original location in the nether fortress. The portal is in a pit that is dug 9 blocks deep (putting it at level 56; i.e., the bottom of the portal frame is level 56). I haven't tested other locations but I suspect you can vary the position quite a bit as long as you are deep enough.
Try it, and good luck! For a real challenge, see if you can get there in Survival Mode with no cheats and no swimming to mainland for more resources. (That means digging to find your own diamonds.) Have fun!
Just for fun: Nether fortress-inspired castle
CLICK HERE for full specifications and examples!