In the NES era, more and more games were being released that were not likely to be finished in a single setting. Adventure games with huge worlds and innumerable secrets were more and more common. While the NES did not invent password saving in console games (Survival Island for the Atari 2600 Supercharger may have that distinction), it certainly popularized it. Cartridge games thereafter (including many Game Boy Advance games) would have to choose between no saving, saving via battery backed memory, rewritable flash memory or EEPROM and the middle ground, passwords.
For the NES, most games that supported anything other than restarting from the beginning after a reset or power down used a password save. Here are some examples of some passwords :
Simple Passwords :
Bubble Bobble allows the player to select a level via a password. Each level is assigned a particular 5 character code, and there are different codes for Bubble Bobble (the first time through) and Super Bubble Bobble (the second time through). If you look at the passwords, you will see a pattern emerge as the level number is incremented by one.
WURM: Journey to the Center of the Earth is even more simple, the passwords are arbitrarily assigned to each act and never change.
Little Sampson's passwords just save the the level you last beat like WURM, but do not save the extra health or the potions you may find.
Character Based Passwords :
64 characters x 24 spaces
Metroid and Kid Icarus use an identical password system from the player's perspective. The passwords are 24 characters long and each password space can select from 64 characters. Typically you will often see that passwords use a number of characters and spaces that correspond to a power of two (32 or 64 characters) or near a power of two (24, 48). In these games' cases, they use A-Z, a-z and 0-9 and a few punctuation marks to make 64.
With 64 characters, you can store the state of six bits. 4 such characters in a row gives you 24 bits or 3 bytes, something the 8-bit NES CPU can easily manage. Thus, with 24 characters, you can store 18 bytes. With these complicated games, almost every bit has some in-game meaning.
Nintendo did not want to make it easy for players to crack their passwords, so they implemented bit shifting and checksums so that random passwords would not be easily accepted and that the password would not necessarily be almost the same every time, even if you made no progress in the game.
Ironically, Metroid and Kid Icarus ended up using boards with an extra memory chip. The only difference between a Metroid PCB and a Legend of Zelda PCB is that the latter has a battery and the extra passive components required for battery-backed saving. It would seem that the original intent was that Metroid and Kid Icarus would have used a board without the extra RAM chip, but late in the porting process from the Famicom Disk System to cartridge, it was discovered that these games required the extra RAM.
Here are other examples of games with similar passwords :
The Goonies 2
48 characters x 14 spaces
Even though this game only uses 48 characters, each bit still represents 6 bits of information, even if not all those bits can be realized
The Guardian Legend/Rambo
64 characters x 32 spaces
These games have an RPG-like experience system, so saving large numbers becomes important.
Wizards and Warriors II
26 characters x 12 spaces
Uses only A-Z, but you still treat it has a a 5-bit value.
Grid-Based Passwords :
Mega Man 2/Mega Man 6
2 characters x 25 spaces
Grid-based passwords are not really that much different from character based passwords and often much simpler. Mega Man 2 & 6 uses a dot within a 5x5 grid. Thus each grid space can be occupied by a dot or not, giving 1 bit for each grid. This password saves 25 bits of information, or just over 3 bytes.
Mega Man 3/5
3 characters x 36 spaces
Only slightly more complicated because there can be one of two colored dots and a 6x6 grid. Each grid must store 2 bits
4 characters x 16 spaces
Each cell can have three symbols (whip, heart, cross) or be blank, so each cell still stores 2 bits. This password is slightly more complicated because the player's name will have an effect on the symbols.
Split Passwords :
Swords and Serpents
32 characters x 20 spaces x 5 passwords
Swords and Serpents may have the longest passwords of any NES game. Each of the four characters have his or her own password and the world state is stored in the fifth password. The character's names have an effect on their passwords as well.
River City Ransom :
63 characters x 33 spaces x 2 passwords
In RCR, each player has a separate password, so the burden of writing down the password is less onerous in a one-player only game. Unlike Swords and Serpents, there is no game world password.
Long Japanese Passwords :
64 characters x 20 spaces
Dragon Quest II
64 characters x 52 spaces
In Japan, all four of the Famicom Dragon Quest games were huge, giving Enix (later Square/Enix) a guaranteed success. Even the remakes sell over a million copies. In the beginning, things were much more humble and the first two Dragon Quest games required the player to enter passwords to continue their game. As the series became more successful and the games larger, Enix ponied up for the extra cost of a battery-backed memory cartridge for III and IV. When released overseas, Nintendo oversaw the localization of the first game and retrofitted it to use a battery backed save. Enix did the same when they ported over II.
Maniac Mansion Japanese Version
66 characters x 104 spaces
Maniac Mansion was first released in Japan and ported by Jaleco. The resulting game may use the longest password of any Famicom or NES game. Maniac Mansion was ported from home computers and space was not quite as precious as it was on a cartridge. The SCUMM engine did not necessarily seem to save a game efficiently. Even though the Japanese version pretty much scraps the SCUMM engine, the same variables needed to be saved. Each character stores 7 bits and this saves 91 bytes worth of information.
How long would a password for The Legend of Zelda have been?
The Legend of Zelda stored far more information about the game than any game before it. Consider what it saves of each of its three save slots :
1. The Character's Statistics
Player name - 1-8 characters
Number of deaths - 0-255
Life Meter - 3-16 Hearts
Rupees - 0-255
Keys - 0-9
Bombs - 0-16
Items : Wooden Sword, Boomerang, Magic Boomerang, Bow, Arrow, Silver Arrow, Food, Large Shield, White Sword, Magic Sword, Raft, Stepladder, Magic Key, Magic Wand, Spell Book, Blue Candle, Red Candle, Blue Ring, Red Ring, Whistle, Red Potion, Blue Potion, Letter, Power Bracelet
Quest Number - 1 or 2
Based on the above, I would estimate it takes 16 bytes to save your character's attributes.
2. The Overworld
The Overworld is on an 8x16 grid, and the all the Underworld screens are on a 16x16 grid.
For every Overworld screen, two types of information are saved. First is the number of enemies remaining. If there is one or more of the enemies on the screen, not including Zoras or Ghosts, the same will save that number, but not the type. I do not recall any screen with more than six enemies. Second are the permanent alterations to the screen caused by blasting a door into a rock with a bomb or burning a tree with one of the candle or by uncovering a warp stairwell. There is no more than one such secret on any given screen. One byte per screen should be sufficient, so this is 128 bytes.
Third are the people inside the caves/stairwells. These include the "It's a Secret to Everybody" Moblins, the old man who makes you pay for his door, and whether the old woman has seen the letter. There are about twenty instances in the First Quest, so that is another 3 bytes.
3. The Underworld
For the Underworld, there are several pieces of information stored:
Hungry Goriya fed - 1 in First Quest
Bomb guy paid? - 2
Triforce Taken? - 8
Compass and map for each level - 18
Boss monsters for each level defeated - about 32 in the First Quest
Room item taken? - Only one item per room unless its a 10 rupee room, which can be a key, a bomb or money - approximately 128 instances
Opened locked door or bombable wall uncovered? - Up to four per screen, approximately 128 instances
Approximately 40 bytes are required to save the Underworld state.
In total, approximately 187 bytes are required for Zelda's save. That is more than double the bytes required for Maniac Mansion Japanese Version. So, assuming a 64 character system like Metroid and Kid Icarus, you would need about a 250 space password to restore your game. Obviously that was not going to work, so either the Disk System or a battery-backed saving system had to be used overseas, and Nintendo chose the latter.