Won't you take a look with me?!
The early days
In a sense, dating all the way back to Nintendo's pre-cartridge home game systems like the Color TV Game 6 and 15, their systems have been region-locked, though ostensibly not intentionally at first. The main problem with these old systems is that they output video and audio only through RF, the frequencies of which tend to differ slightly between American and Japanese televisions. If you try playing them on a more modern television that can't fine-tune to find signals between channels, you are pretty much outta luck. The Famicom is much the same way, though it can be modified to output via RCA jacks (and the later AV Famicom model works universally fine). Speaking of the Famicom though...
The Famicom and NES: Serious business
The Famicom/NES had some pretty tricky actual region locking. The main incompatibility between the two systems is the actual design of the game cartridges. Famicom games have a connector board that has 60 pins, while the NES features a cartridge connector that accepts 72-pin games of the non-Famicom variety only. The physical size of Famicom cartridges is also smaller, meaning they won't actually be able to fit into the NES, with its deep cartridge tray. This can be worked around with a "cartridge converter" for the most part, which maps the pins to a smaller connector and pads out the empty space inside the NES, allowing the cart to fit, though there are some quirks when playing a Famicom game on an American NES.
Funnily enough, Nintendo changed the design of the cartridge connector in America to give the NES extra pins to communicate with via the expansion port on the bottom of the NES, in case of future hardware expansions (back when it was known as the AVS and was planned to be the centerpiece of a computing system). In exchange, they dropped a few of the pins that the Japanese games used to communicate with the system itself. That means that if you play certain games that contain extra sound hardware, like Gimmick! or Akumajou Densetsu (Japan's version of Castlevania III), you won't be able to hear the added tunes.
Some of those extra pins on the US NES cartridges interfaced with Nintendo's own "actual" authentication mechanism, the "10NES" chip. The NES checks for a special chip inside any cartridge it tries to run, and if it doesn't detect one it will just reset (the infamous "blinking screen of death"). Since Famicom games don't contain the chip, they'll never boot even if you can get them connected... unless you either disable the chip inside the hardware itself through a relatively easy modification, or use a cartridge converter that itself contains one of the 10NES chips. Phew!
Super NES and Nintendo 64: Physical challenge
The Super Nintendo also underwent some changes when it arrived in the States about ten months after the Super Famicom hit Japan. Though the cartridge boards are essentially identical between Super Famicom and Super Nintendo games, the plastic cartridge shells that the games are housed in are slightly different between regions. Super Nintendo games have small plastic notches towards the bottom, with matching plastic nubs resting inside the system. The plastic notches inside the cartridge slot prevent Japanese games from being inserted, since they don't have the same nubs in the cases!
There are a couple solutions to this problem. Perhaps the easiest is simply to plug the Japanese game onto a Game Genie, which fits into the SNES, and play it that way. Another method is to physically remove the nubs from the cartridge slot with a dremel or pair of pliers. Where it gets trickier is the other way around, playing Super Nintendo games on a Super Famicom. The Super NES cartridges are more square in shape, while the SFC games are more roundy, and as a result the Super NES games won't even fit into the Japanese slot at all. You can either remove the entire top of the system, use the Game Genie method, buy a cartridge converter, or, perhaps most annoyingly, put the Japanese game's circuitboard into a Super NES game's cartridge case through the use of a security game bit.
The last cartridge-based home console from Nintendo, the Nintendo 64's region lockout worked in pretty much the same way as the Super Nintendo's, though even more simplified. The tabs inside the cartridge slot changed positions depending on the region of your game, but the cartridge sizes and fronts were identical between regions. Solution: either modify the cartridge slot to remove the tabs, or swap case backs depending on the region of the game you want to play. For better or worse, there weren't many Nintendo 64 games worth importing—most gamers who dabbled in such things only ran into this problem when shipping a copy of Sin and Punishment over from Japan to discover the damned thing didn't fit.
GameCube, Wii, and the future
Of course, with disc-based media came another basket of worms. The GameCube, though, didn't require anything more involved than older systems like the Sega Mega Drive/Genesis. All the Cube needs is a single wire soldered to a point on the motherboard, and attached to a switch. Throwing the switch in either direction changes regions between Japan and the U.S. at will. And our treasured Wii has a succession of stories. At first there were modchips that accomplished region-free gaming, though they were locked out later with hardware and firmware revisions, a new concept in the always-on Internet age. Soft modifications later took the place of physical mods, though a system that was region-free one day could be de-modded the next by a firmware update, making it a constant battle. For the most part though, software soft modifications were left generally alone by Nintendo in the system's twilight years, offering a pretty reliable region-free workaround.
And so we come to the Wii U, which will no doubt be even more locked down than the Wii was—and all signs point to this one being not nearly as easy to circumvent. Now that our systems are connected to the Internet all the time, and are basically reliant on it for essential game services like online play and purchases, it's easier than ever for companies to verify the tampered-with-ness of any systems we use to connect to their network. Nintendo's recent foray into seemingly unbreakable region-locking with the 3DS has proven ironclad almost two years after its release, and there's no reason to believe that they'll make things any easier with the Wii U.
Ultimately the fact that we now have access to a pretty considerable selection of games translated into our own languages, purchasable without even leaving the house, numbs the sting of exclusion a bit. But it's wrong to act like this is anything new. They've been throwing up little fences for almost thirty-five years!