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. The actual set contents were indicated on the inner tray. This set is 700/5.
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").