tl;dr
"Foo" and "bar" as metasyntactic variables were popularised by MIT and DEC, the first references are in work on LISP and PDP-1 and Project MAC from 1964 onwards.
Many of these people were in MIT's Tech Model Railroad Club, where we find the first documented use of "foo" in tech circles in 1959 (and a variant in 1958).
Both "foo" and "bar" (and even "baz") were well known in popular culture, especially from Smokey Stover and Pogo comics, which will have been read by many TMRC members.
Also, it seems likely the military FUBAR contributed to their popularity.
The use of lone "foo" as a nonsense word is pretty well documented in popular culture in the early 20th century, as is the military FUBAR. (Some background reading: FOLDOC FOLDOC Jargon File Jargon File Wikipedia RFC3092)
OK, so let's find some references.
STOP PRESS! After posting this answer, I discovered this perfect article about "foo" in the Friday 14th January 1938 edition of The Tech ("MIT's oldest and largest newspaper & the first newspaper published on the web"), Volume LVII. No. 57, Price Three Cents:
On Foo-ism
The Lounger thinks that this business of Foo-ism has been carried too far by its misguided proponents, and does hereby and forthwith take his stand against its abuse. It may be that there's no foo like an old foo, and we're it, but anyway, a foo and his money are some party. (Voice from the bleachers- "Don't be foo-lish!")
As an expletive, of course, "foo!" has a definite and probably irreplaceable position in our language, although we fear that the excessive use to which it is currently subjected may well result in its falling into an early (and, alas, a dark) oblivion. We say alas because proper use of the word may result in such happy incidents as the following.
It was an 8.50 Thermodynamics lecture by Professor Slater in Room 6-120. The professor, having covered the front side of the blackboard, set the handle that operates the lift mechanism, turning meanwhile to the class to continue his discussion. The front board slowly, majestically, lifted itself, revealing the board behind it, and on that board, writ large, the symbols that spelled "FOO"!
The Tech newspaper, a year earlier, the Letter to the Editor, September 1937:
By the time the train has reached the station the neophytes are so filled with the stories of the glory of Phi Omicron Omicron, usually referred to as Foo, that they are easy prey.
...
It is not that I mind having lost my first four sons to the Grand and Universal Brotherhood of Phi Omicron Omicron, but I do wish that my fifth son, my baby, should at least be warned in advance.
Hopefully yours,
Indignant Mother of Five.
And The Tech in December 1938:
General trend of thought might be best interpreted from the remarks made at the end of the ballots. One vote said, '"I don't think what I do is any of Pulver's business," while another merely added a curt "Foo."
The first documented "foo" in tech circles is probably 1959's Dictionary of the TMRC Language:
FOO: the sacred syllable (FOO MANI PADME HUM); to be spoken only when under inspiration to commune with the Deity. Our first obligation is to keep the Foo Counters turning.
These are explained at FOLDOC. The dictionary's compiler Pete Samson said in 2005:
Use of this word at TMRC antedates my coming there. A foo counter could simply have randomly flashing lights, or could be a real counter with an obscure input.
And from 1996's Jargon File 4.0.0:
Earlier versions of this lexicon derived 'baz' as a Stanford corruption of bar. However, Pete Samson (compiler of the TMRC lexicon) reports it was already current when he joined TMRC in 1958. He says "It came from "Pogo". Albert the Alligator, when vexed or outraged, would shout 'Bazz Fazz!' or 'Rowrbazzle!' The club layout was said to model the (mythical) New England counties of Rowrfolk and Bassex (Rowrbazzle mingled with (Norfolk/Suffolk/Middlesex/Essex)."
A year before the TMRC dictionary, 1958's MIT Voo Doo Gazette ("Humor suplement of the MIT Deans' office") (PDF) mentions Foocom, in "The Laws of Murphy and Finagle" by John Banzhaf (an electrical engineering student):
Further research under a joint Foocom and Anarcom grant expanded the law to be all embracing and universally applicable: If anything can go wrong, it will!
Also 1964's MIT Voo Doo (PDF) references the TMRC usage:
Yes! I want to be an instant success and snow customers. Send me a degree in: ...
Foo Counters
Foo Jung
Let's find "foo", "bar" and "foobar" published in code examples.
So, Jargon File 4.4.7 says of "foobar":
Probably originally propagated through DECsystem manuals by Digital Equipment Corporation (DEC) in 1960s and early 1970s; confirmed sightings there go back to 1972.
The first published reference I can find is from February 1964, but written in June 1963, The Programming Language LISP: its Operation and Applications by Information International, Inc., with many authors, but including Timothy P. Hart and Michael Levin:
Thus, since "FOO" is a name for itself, "COMITRIN" will treat both "FOO" and "(FOO)" in exactly the same way.
Also includes other metasyntactic variables such as: FOO CROCK GLITCH / POOT TOOR / ON YOU / SNAP CRACKLE POP / X Y Z
I expect this is much the same as this next reference of "foo" from MIT's Project MAC in January 1964's AIM-064, or LISP Exercises by Timothy P. Hart and Michael Levin:
car[((FOO . CROCK) . GLITCH)]
It shares many other metasyntactic variables like: CHI / BOSTON NEW YORK / SPINACH BUTTER STEAK / FOO CROCK GLITCH / POOT TOOP / TOOT TOOT / ISTHISATRIVIALEXCERCISE / PLOOP FLOT TOP / SNAP CRACKLE POP / ONE TWO THREE / PLANE SUB THRESHER
For both "foo" and "bar" together, the earliest reference I could find is from MIT's Project MAC in June 1966's AIM-098, or PDP-6 LISP by none other than Peter Samson:
EXPLODE, like PRIN1, inserts slashes, so (EXPLODE (QUOTE FOO/ BAR)) PRIN1's as (F O O // / B A R) or PRINC's as (F O O / B A R).
Some more recallations.
@Walter Mitty recalled on this site in 2008:
I second the jargon file regarding Foo Bar. I can trace it back at least to 1963, and PDP-1 serial number 2, which was on the second floor of Building 26 at MIT. Foo and Foo Bar were used there, and after 1964 at the PDP-6 room at project MAC.
John V. Everett recalls in 1996:
When I joined DEC in 1966, foobar was already being commonly used as a throw-away file name. I believe fubar became foobar because the PDP-6 supported six character names, although I always assumed the term migrated to DEC from MIT. There were many MIT types at DEC in those days, some of whom had worked with the 7090/7094 CTSS. Since the 709x was also a 36 bit machine, foobar may have been used as a common file name there.
Foo and bar were also commonly used as file extensions. Since the text editors of the day operated on an input file and produced an output file, it was common to edit from a .foo file to a .bar file, and back again.
It was also common to use foo to fill a buffer when editing with TECO. The text string to exactly fill one disk block was IFOO$HXA127GA$$. Almost all of the PDP-6/10 programmers I worked with used this same command string.
Daniel P. B. Smith in 1998:
Dick Gruen had a device in his dorm room, the usual assemblage of B-battery, resistors, capacitors, and NE-2 neon tubes, which he called a "foo counter." This would have been circa 1964 or so.
Robert Schuldenfrei in 1996:
The use of FOO and BAR as example variable names goes back at least to 1964 and the IBM 7070. This too may be older, but that is where I first saw it. This was in Assembler. What would be the FORTRAN integer equivalent? IFOO and IBAR?
Paul M. Wexelblat in 1992:
The earliest PDP-1 Assembler used two characters for symbols (18 bit machine) programmers always left a few words as patch space to fix problems. (Jump to patch space, do new code, jump back) That space conventionally was named FU: which stood for Fxxx Up, the place where you fixed Fxxx Ups. When spoken, it was known as FU space. Later Assemblers ( e.g. MIDAS allowed three char tags so FU became FOO, and as ALL PDP-1 programmers will tell you that was FOO space.
Bruce B. Reynolds in 1996:
On the IBM side of FOO(FU)BAR is the use of the BAR side as Base Address Register; in the middle 1970's CICS programmers had to worry out the various xxxBARs...I think one of those was FRACTBAR...
Here's a straight IBM "BAR" from 1955.
Other early references:
1973 foo bar International Joint Council on Artificial Intelligence
1975 foo bar International Joint Council on Artificial Intelligence
I haven't been able to find any references to foo bar as "inverted foo signal" as suggested in RFC3092 and elsewhere.
Here are a some of even earlier F00s but I think they're coincidences/false positives: