I think to have heard that the Cookie Monster first appeared in a commercial rather than Sesame Street itself. Is this true? If not, where was Cookie Monster's first appearance if not in Sesame Street?
He wasn't known as "Cookie Monster" yet, but he did make several appearances before Sesame Street.
The book Jim Henson's Designs and Doodles explains Cookie Monster's origin as follows: "In 1966, Henson drew three monsters that ate cookies and appeared in a General Foods commercial that featured three crunchy snack foods: Wheels, Crowns and Flutes. Each snack was represented by a different monster. The Wheel-Stealer was a short, fuzzy monster with wonky eyes and sharply pointed teeth. The Flute-Snatcher was a speed demon with a long, sharp nose and windblown hair. The Crown-Grabber was a hulk of a monster with a Boris Karloff accent and teeth that resembled giant knitting needles."
"These monsters had insatiable appetites for the snack foods they were named after. Each time the Muppet narrator, a human-looking fellow, fixes himself a tray of Wheels, Flutes and Crowns, they disappear before he can eat them. One by one, the monsters sneak in and zoom away with the snacks. Frustrated and peckish, the narrator warns viewers that these pesky monsters could be disguised as someone in your own home, at which point the monsters briefly turn into people and then dissolve back to monsters again."
As it turns out, these commercials were never aired — but all three monsters had a future in the Muppet cast. The "Crown-Grabber" was used in a sketch on The Ed Sullivan Show, in which he ruins a girl's beautiful day. Known from then on as the Beautiful Day Monster, he made a number of appearances on Sesame Street and The Muppet Show. The "Flute-Snatcher" turned into Snake Frackle, a background monster from The Great Santa Claus Switch and The Muppet Show.
In 1967, Henson used the "Wheel-Stealer" puppet for an IBM training film called Coffee Break Machine. In the sketch, called "The Computer Dinner", the monster (with frightening eyes and fangs) devours a complex coffee making machine as it describes its different parts. When he is finished, the machine announces the monster has activated the machine's anti-vandalism system, which contains the most powerful explosives known to man. The monster promptly explodes. This sketch was also performed in October, 1967 on The Ed Sullivan Show. It was also later performed on the George Burns episode of The Muppet Show' using the Luncheon Counter Monster.
Two years later, Henson used a similarly-designed and equally ravenous monster for three commercials selling Munchos, a Frito-Lay potato chip. This time, the puppet was called Arnold, the Munching Monster. After the three ads were produced, Henson had the opportunity to renew the contract. He chose not to, because at that point he was working on Sesame Street — and that monster puppet was moving on to the next stage in his career. According to Frank Oz, in a later routine the then unnamed monster won a quiz show and for winning was "given the choice of $10,000 cash, a new car, a trip to Hawaii, or a cookie." He took the cookie and from then on he was Cookie Monster.
Cookie Monster, still unnamed, made his Sesame Street debut in the first episode, interfering with Kermit the Frog's "famous W lecture" by eating a model "W" bit by bit. He turns it into an "N," a "V," and finally an "I," to Kermit's frustration. He then tries to eat Kermit.
It was during the first season that Cookie Monster got his name and began using the growly vernacular (e.g., "Me eat cookie!") that would become part of his character. His signature song, "C Is For Cookie", was first aired during the 1971–72 season, and became one of the best-known songs from Sesame Street.