NES was available in some parts of Europe almost at the
same time it was available in the US. It first debuted in
1986, with local distributors releasing it in Scandinavia
and Germany. In 1987, Mattel signed a deal with Nintendo
of Japan to distribute the NES in Australia, New Zealand,
the UK and Italy. Mattel did all right in Oz, but mostly
failed in Europe, whose NES division treated the console
like a mere toy in advertising.
Countries mid-Europe (France, Germany, the Netherlands) were handled by Nintendo International, an independent company of Nintendo themselves, and the company that took over Mattel's UK distribution in early 1990. Mattel still held on to Italy until 1991, meaning that the NES had almost zero penetration in that country. This sort of hodgepodge distribution scheme in Europe was the main reason for the Sega Master System's superior sales in Europe, and the situation didn't improve for Nintendo until it finally set up shop itself in Germany.
How popular was the NES in Europe? Several game mag articles have said that it was like the popularity of the NES over the SMS in the USA, only the opposite. This isn't entirely true, though; Nintendo International countries did fairly well with the console and by 1990, about 12 percent of French households owned a NES. Nintendo International also published their own Nintendo Power clone, called Club Nintendo, in several languages. Unlike NP it was (is?) a free newsletter and had a circulation of about 800,000 at its prime.
Admittedly, though, this isn't the sort of dominance that Nintendo had in the USA. Nintendo didn't really hit it big in Europe until the introduction of the Game Boy, which was an instant success.The NES was a mild success in Australia, and Mattel's division sublicensed a few dozen games from American and Japanese companies. Beam Software, makers of Smash TV, Dash Galaxy in the Alien Asylum and a lot of other so-so NES games, were based in Australia and produced one or two games exclusively for the locals, most notably the only sim I've seen of the best sport ever Aussie Rules Footy.
Add to this the slightly mysterious company HES (Home Entertainment Suppliers), an Australia-only unlicensed third party whose method of getting around Nintendo's lockout chip involved a dongle which you had to insert a licensed NES cart into. (Codemasters used a similar tactic for their UK releases - they simply put their games in Game Genie cases.) Although not really a pirate company, all of their games come from Sachen, BIT Corp. and other Taiwan/Hong Kong manufacturers. Some HES releases have not seen official NES-cart release anywhere else, making a couple of them interesting to collectors.
The carts themselves are the same design as American NES carts; however, there are country locks on the carts. Meaning, that one could only play a certain cart on a NES that was bought in the same country (or general area) as the cart; otherwise the game would be locked out. Naturally, this state of affairs bought about a slew of convertors and adapters for the Euro audience, including adapters that allowed one to play any type of NES cart - including American ones.
Also, as you might expect, there were more than a few games released in Europe only, not to mention things like name changes for the European audience. PAL only games include the computer classic Elite (the ROM of which was recently released as freeware), Asterix, The Smurfs, Aussie Rules Footy (heh), and games based on Disney moves Aladdin and The Lion King. FC Parodius was also released in Europe by Palcom (the European version of Konami's Ultra label).
A list of PAL-only releases and name changes from NTSC to PAL versions would be a great idea, but there's certainly still a lot of information that needs to be collected about PAL releases before it can be a reality.
Thanks to Niels, Chris Coleman and many others for the scans currently on this page. Some more:
Corvette ZR-1 Challenge (box) from Milton Bradley