They weren’t just Scouts either. The Bangkok Post just ran the strips where Charlie Brown et al are at the beach – some lake – and Snoopy and his “pirate band” land on shore. They all wore eye patches, especially Conrad, who had a patch over both eyes. Linus wondereed what they were here to pillage for, and it seems it was for ice cream.
He actually appears for the first time a few months before the 1967 Halloween strip, on July 12 and 13, 1967, when Snoopy sees him and thinks “Now I’ve seen everything … a bird hippie!”, then has a discussion with him on how nobody understands his generation.
The Fantagraphics people seem to think that’s Woodstock too. If he was indeed on of the baby birds born on Snoopy’s stomach – which is a reasonable supposition, certainly – my belief is that the “bird hippie” is indeed him, and that he went through a hippie phase and named himself Woodstock before cutting his hair and getting a job as Snoopy’s secretary. 
And occasionally they were French Foreign Legion soldiers from Beau Geste, defending Fort Zinderneuf.
Oddly enough, the Peanuts FAQ has this to say about when Woodstock first appeared:
Man, controversy abounds.
Okay, my Peanuts-fu is really strong today. I was able to find the strips with very little trouble!
I was wrong in that the bird hippie character is introduced in two mid-1967 strips, just with Snoopy, who expresses some snark at his appearance. The hippie makes what I think is his final appearance in the aforementioned Great Pumpkin strip (though it was just Linus & Snoopy sitting in wait, not Sally/Peppermint Patty).
The hatchling who can’t fly, however, also appears in early and late 1967, and I don’t think he’s meant to be the same character as the bird hippie. But I gotta believe this hatchling is proto-Woodstock, whose lack of flying ability is canon.
Early 1967 reappearance of the hatchling/proto-Woodstock
Mid-1967 introduction of the bird hippie
(There’s a strip in Autumn 1967 that shows the hatchling flying (badly) South for the winter. The poor thing starts heading North, naturally, before correcting himself.)
Halloween 1967 strips with the bird hippie as punchline.
The hippie doesn’t appear in subsequent strips that year.
Edited to add: Blimey! chorpler was faster than I was. But believe it or not, I have to disagree with the Fantagraphics folks. Everything to me indicates that the 1965 or 66 hatchling who sucks at flying, who hangs out often with Snoopy, is the same little bird who turns into Woodstock.
Here’s some lovely quotes by Schulz from the Charles M Schulz museum:
FIRST APPEARED APRIL 4, 1967 ? MENTIONED BY NAME JUNE 22, 1970
“Woodstock has been many birds. He appeared gradually as I discovered I was drawing this one little bird more and more. It seemed only natural to call him Woodstock. He’s Snoopy’s friend and confidant. He just worships Snoopy and would do anything for him, even type his letters for him.” (1971)
“I named Woodstock, the bird, after the festival. Some people think he’s a bat or a butterfly. That’s Woodstock’s problem. He doesn’t know who he is. But I can do beautiful things with him - like the time he and Snoopy went camping, Woodstock makes a little pillow out of twigs and gazes up at a huge moon. Just then a flock of geese flies over. You know and he knows he’ll never be able to do anything like that.” (1972)
“Woodstock knows that he is very small and inconsequential indeed. It’s a problem we all have. The universe boggles us. In the larger scheme, we suddenly realize, we amount to very little. It’s frightening. Only a certain maturity will make us able to cope. The minute we abandon the quest for it we leave ourselves open to tragic results. Woodstock is a lighthearted expression of that idea.” (1980)
—Charles M. Schulz
I’m going to propose Schulzus sparkinkia as the official name of our good friend Woodstock. Any taxonomists here are free to correct my on the fly try.
Now I’m picturing Snoopy banging the doghouse and bellowing “WOODSTOCK!!” the way Ari bangs his desk and bellows “LLOYD!!” on Entourage.
Wikipedia also mentions the special She’s A Good Skate, Charlie Brown, which contains what has to be Woodstock’s finest moment. Background: There is or was this guy who can whistle opera (for real). He contacted Schulz/Melendez and offered his services, should they ever want to have Woodstock sing. “Interesting,” they thought, and forgot about it until they were working on the above-named special. In it, Peppermint Patty is taking part in a figure-skating competition, and her music is the aria O mio babbino caro. Follow the link and see if it doesn’t bring a tear to your eye.
And Woodstock is a burd.
Also notable about that Good Skate video: Is that the only time we hear an adult speaking coherently in a Charlie Brown cartoon?
He can’t be a dog – he wears a hat and drives a car.