What was the first Lego set produced, and when was it first released?
Some of the earliest "LEGO brick" sets I could find were these three on BrickLink from 1954:
As other answers have noted, there were earlier sets than this, but they were referred to as "Automatic Binding bricks". It wasn't until 1953 that the bricks were officially renamed as "LEGO bricks" (i.e. "LEGO Mursten").
These sets were using precursor designs of the "modern" plastic LEGO brick without the hollow underside tube. It wasn't until 1958 that the brick design we all know and love today was created. It was officially "born" at exactly 1:58 p.m., January 28, 1958, when it was first patented.
So, if you're looking for the earliest official "LEGO bricks" using the modern stud-and-tube design, these are the sets you're looking for:
A detailed timeline of Lego's history is layed out here dating back to the initial birth of the company.
We see from this that the first Lego-like bricks was the Kiddicraft Self-Locking Building Brick marketed by Hilary Fisher Page in England in 1947. This was the forerunner to Lego, and in 1949, the Lego company begins production of Automatic Binding Brick in Denmark.
This is the Automatic Binding Brick set 700/3.
Here is a detailed article on the origin of the first patented Lego bricks from 1958, designed by Godtfred Kirk Christiansen, who had just taken over as Director after his father. This is the first Lego bricks as we know them today that got a unique system that improved the interlocking dramatically. This new design would become the modern, or as Godtfred called it, the “real” Lego brick. It was the beginning of Lego as we know it today.
Here is the first box image used for all the earliest sets from 1958.
According to Brick Fetish:
Sets of "Automatic Binding Bricks" were first produced in 1949 in Denmark. Sets included 700/1, 700/2, 700/3 and 700/4, with 700/1 being the largest of these sets and 700/4 being the smallest.
In 1950 the 700/3A (between 3 and 4 in size), 700/5 and 700/6 sets were released. The gift sets were boxes of elements hand packaged in a zig-zag pattern in a shallow box.
The bricks themselves didn't carry the LEGO branding - it wasn't until 1953 that the bricks would be called "LEGO Mursten" (danish for "LEGO Bricks").
The first plastic bricks produced by TLG were in 1949, known as Automatic Binding Bricks. The bricks themselved did not have LEGO printed on them.
By 1952 the Automatic Binding Bricks sets started having the LEGO logo (the small fancy one used on TLG wooden toys) in the lower right corner as an added decal, but continued having Automatic Binding Bricks on the box top.
Then in late 1952 they added "LEGO Mursten" to the top of the box (instead of a decal), but continued with the Automatic Binding Bricks box logo.
It wasn't until 1953 that a new box design came out with just "LEGO Mursten". Since "Mursten" is the same word for building bricks in Danish, Norwegian and Swedish, as those countries came online to LEGO sales (Nov. 1953 for Norway, Mar. 1955 for Sweden) they also had LEGO Musten on the box top (although some early Norway sets had Automatic Binding Bricks on the boxes).
Then in late 1955 LEGO boxes started having new box designs with "LEGO System of Play" in the local language on the box tops. German LEGO sales started in March 1956, with Switzerland and Netherlands coming online in early 1957.
Boxes had "System i leg" for Denmark, "System i lek" for Sweden/Norway, "System im Spiel" for Germany/Austria, Systeem bij het Spel" for Netherlands, and "System im Spiel"/"System dans le jeu" for Switzerland. By the time Belgium and Portugal came online at the end of 1957, the decision was to switch to international "LEGO System". The countries already in the local languages had their boxes switch over to the international writing by 1960 (everyone else was done by 1959, but Denmark was the last holdout by 1960).
When the first bricks (2x2 and 2x4 sizes) were introduced (as Automatic Binding Bricks) in 1949, they had no LEGO markings anywhere on the bricks. By 1953 the first bricks had "LEGO" printed only on the hollow underside of the brick. In 1953 1x2 and 2x3 bricks were also introduced, only only found with the logo on the underside. In 1954 the 2x8 and 2x10 bricks were introduced, and the 4x4 corner, (shortlived) 2x12 and 2x14 bricks, and 1x1 round and square bricks were introduced in January 1955.
Then by mid 1955, the new Town Plan series of specialty parts (including 4 types of macaroni bricks, 1x6/1x8 bricks with and without names) and large LEGO plates were introduce.
The first LEGO baseplates were 10x20 size... introduced in 1950 in a 1/2 brick thickness. By 1953 the thin 10x20 was replaced by a 1 brick tall baseplate, and produced for many years.
Gary Istok (Information used in my Unofficial LEGO Sets/Parts Collectors Guide (1949-1990s), confirmed by TLG Archives in Billund.