Foo and bar come from the US Army WWII acronym FUBAR, "F-ed Up Beyond All Recognition". A whole family of these terms came into widespread use during the North African and Sicilian campaigns (1942-43). Rick Atkinson's excellent Day of Battle: The War in Sicily and Italy, 1943-1944 gives a list of these. For instance a JANFU is a "Joint Army Navy F Up", such as the incident on 11 July 1943 when the invasion fleet for Operation Husky shot down 23 Army Air Force C-47 transports carrying paratroopers to reinforce the beachhead.
Update: Wikipedia has a list of related acronyms that includes some the original WWII ones listed by Atkinson.
Any programmer will understand the motivation for using foo and bar to name variables. They certainly have been part of the C/UNIX culture from the start, and as @Walter Mitty points out, predated it.
Update (10/5/2009): Here's Atkinson's description:
Their pervasive "civilianness" made them wary of martial zeal. "We were not romantics filled with cape-and-sword twaddle," wrote John Mason Brown, a Navy Reserve lieutenant headed to Sicily. "The last war was too near for that." Military life inflamed their ironic sensibilities and their skepticism. A single crude acronym that captured the soldier's lowered expectations -- SNAFU, "situation normal, all fucked up" -- had expanded into a vocabulary of GI cynicism: SUSFU (situation unchanged, still fucked up); FUMTU (fucked up more than usual); JANFU (joint Army-Navy fuck-up); JAAFU (joint Anglo-American fuck-up); FUAFUP (fucked up and fucked up proper); and FUBAR (fucked up beyond all recognition) [Atkinson, p. 36].
Update (11/23/2011): @Hugo has a fantastic list of the non-military antecedents.