Lambda the Ultimate

...but there is a famous children's participatory musical piece called "Hello World!", where children are exhorted to greet the world in seven languages. I'm guessing that's where the idea is from.

Google tells me the piece is from 1958, that it was written by William Mayer & Susuan Otto, and that Elizabeth Roosevelt was the narrator in a recording of it.

Kernighan, 1973, A tutorial introduction to the programming language B nearly has a "Hello, world" example illustrating the use of strings:

External variables may be initialized to string values simply by following their names by strings, exactly as for other constants. These definitions initialize a, b, and three elements of v:

a "hello"; b "world'*;

v[2] "now is the time", "for all good men",
"to come to the aid of the party";

Hello, sailor! is immemorially old, but was apparently used in the old days at SAIL (the Stanford AI Lab) before getting written into Zork at about the same time as the first edition of K&R. Perhaps it was a login greeting on SAIL machines: the Jargon File is maddeningly vague.

Maybe that is too pragmatic...

Here is his home page: http://www.cs.princeton.edu/~bwk/

Thanks for all the suggestions. My first conclusion is that it's not that there's an obvious answer that I failed to remember...

Hello World: An Instance Rhetoric in Computer Science discusses the historical background of when, why and how "hello world" became an important phrase for a computer to display. Unfortunately it doesn't have an answer to Ehud's question beyond "the history of this tradition is not well documented" and, like Charles' comment, suggests that the original use in example programs was in B.