The 1955 Bedford Esso truck sets that oddTodd refers to were the earliest appearance of a company name/logo on a product in the LEGO system, however these trucks were sold separately as part of the Town Plan, without bricks (although some versions of the 1251 set came with 1x1 bricks that were used as oil cans). An accessory set from 1955 included gas pumps and a printed Esso sign, but no building elements.
The first regular building set to include a company logo or name was 1310 Esso Filling Station from 1956. The next building sets to include a company name and logo were 306 VW Garage and 307 VW Auto Showroom, both released in 1958. (The first use of the VW logo was on the first 1:87 scale car LEGO produced in 1956, the VW Bus.)
Usage of the Esso name ended in Europe and Australia in 1965 and in the US in 1966. In 1966 the Shell brand name was first used in set 325 Shell Service Station