Which is correct, "on-line" or "online"?

Both are acceptable; usage depends upon the audience you're writing for, and then your personal writing style/personal taste, in that order.

There are many words in English which can be hyphenated according to personal preference, and often hyphenation provides greater clarity over non-hyphenation. Generally, in formal, professional writing, the decision to hyphenate or not will be made by the editorial staff for which one is writing. At the academic level, however, this decision will be made either by the professor, or -- if not -- devolve to the author him/herself.

However, as simchona's N-Gram indicates, "online" is currently gaining preference over "on-line". For my part, I tend to use one or the other, depending on context and rhetorical aim. For instance, I tend to hyphenate when the word is used as a predicate complement ("I am on-line", "I need to get on-line"), and use the non-hyphenated version when it's just a straight adjective ("It's an online game", "Online accounts are down, right now"). But these aren't hard and fast, even for me; if I'm writing for younger audiences, I will tend to just go with "online", because that seems to be how things are trending with their age group.

I would do just the opposite of what you do. In other words, if I'm using it as an adjective, I would do what one has always done when two words form one adjective--use a hyphen. Hence: "It's an on-line project." I am also out of step with the rest of the world in that I see two words, period, when the expression is used as what you call a predicate complement: "I am on line" is how my brain would write it.

I have been a newspaper editor for 47 years in Houston. Try thinking of it this way. "On-line" and "online" are just short for "on the line," the line being your connection to the World Wide Web. So we really have three choices. As we say in advertising, "Pick the one that's best for you."

Now, after I initially posted this, I had this thought: Consider "on the phone" (or in today's world, "on the cell"). We have not evolved to "on-phone" or "onphone." So, I'm beginning to think that maybe we go back to the future and use "on the line."

Now I feel so much more refreshed.

It seems to me that there is a very slight difference between the original version ("on-line operation") and the modern use ("to go online"). In 1950, being "on-line" meant that a device was working over a line of communication ("on the line" as someone else pointed out). Now "being online" describes a full user experience, and not just the method by which their computer is connected. This change in meaning occurred in the 1990s when people started spending more time "online."

It's possible that as the term became more common, lazy typists began to opt out of the hyphen.

Computer and internet grammar has evolved rapidly since the late 1980s. You rarely see people saying they're going to be "on the World Wide Web" anymore, nor do you see "Internet" capitalized much, as was common 20 years ago.