Why do we say the outcome variable "is regressed on" the predictor(s)? Is there some intuitive explanation for this terminology? Why is it this way, and not the predictor(s) being regressed on the outcome?
Ideally I'm hoping that a proper explanation of why this terminology exists will help students remember it, and stop them from saying it the wrong way around.
 A: I've often used and heard this way of speaking. I'd guess that the sequence mentioning the outcome or response before the predictors follows from conventions in writing, using words or using notation or mixing the two,  all the way up to 
$Y = X\beta$ 
setting aside the equally interesting (or uninteresting!) question of what we call different kinds of variables. 
But it seems equally valid mathematically and statistically to mention the predictors first, just as many mathematicians write mappings or functions with arguments first. 
What often perhaps drives the sequence we use in statistical discussions is that scientifically or practically we usually have a clear idea of what we are trying to predict -- it is mortality, or income, or wheat yield, or votes in an election, or whatever -- while the pool of potential or actual predictors may not be so clear. Even if it is clear, it makes sense to mention the important things first. What are you trying to do? Predict whatever. How are you going to do it? Use some or all of these variables. 
I don't have a story for "on" rather than any other word that would fit. I don't hear "regressed against" or "regressed with". There may be no logic here, just memes passed on along in textbooks, teaching and discussions. 
In general, watch out. Consider a related issue, the meaning of "versus". I was brought up to say "plot  $y$ [vertical axis variable] against (or versus) $x$ [horizontal axis variable]" and the reverse sounds singularly odd to me. Nevertheless people with considerable experience and expertise have it the other way round. Sometimes, this kind of difference might be traced to charismatic and idiosyncratic  teachers who you have imitated ever since you sat at their feet. 
A: 1) The term regression comes from the fact that in the usual simple linear regression model:
$y = \alpha + \beta x + \epsilon$
that unless the outcome, $y$, and predictor, $x$, variables are perfectly correlated, the fitted values, $\hat{y}$,  are closer to the mean of the outcome, $\bar{y}$, (after standardization) than the predictor variable, $x$, is to its mean, $\bar{x}$ (after standardization).  Thus the outcome exhibits regression toward the mean.
$|\hat{y} - \bar{y}| / s_y < |x - \bar{x}| / s_x $
For example if we use the BOD data frame built into R then:
fm <- lm(demand ~ Time, BOD)
with(BOD, all( abs(fitted(fm) - mean(demand)) / sd(demand) < abs(scale(Time))))
## [1] TRUE

For a a proof see: https://en.wikipedia.org/wiki/Regression_toward_the_mean
2) The term on comes from the fact that the fitted values are the projection of the outcome variable onto the subspace spanned by the predictor variables (including the intercept) as further explained in many sources such as http://people.eecs.ku.edu/~jhuan/EECS940_S12/slides/linearRegression.pdf .
Note
Regarding the comment below, what the commenter is stating is what the answer already states above in formula form except that the answer states it correctly.  In fact, due to the equality:
$(\hat{y} - \bar{y}) = \hat{\beta} (x - \bar{x}) $
the dependent variable is not necessarily on average closer to its mean than the predictor is to its mean unless $| \beta | < 1$ .  What is true is that the dependent variable is on average fewer standard deviations from its mean than the predictor is to its as stated in the formula in the answer.
Using Galton's data to which the comment refers (which is available in the UsingR package in R) we run the regression and in fact the slope is 0.646 so the average child was closer to its mean than its parent was to its mean but that is not the general case.
library(UsingR)
fm2 <- lm(child ~ parent, galton)
coef(fm2)[[2]] # slope
## [1] 0.646

The BOD example in (1) above is one where the dependent variable is not closer to its mean unless one measures closeness in standard deviations as the slope > 1.
coef(fm)[[2]] # slope
## [1] 1.7214 

with(BOD, all( abs(fitted(fm) - mean(demand)) < abs(Time - mean(Time))))
## [1] FALSE

A: I do not know what the etymology of "is regressed on" is but here is the interpretation that I have in mind when I am saying or hearing this expression. Consider the following figure from The Elements of Statistical Learning by Hastie et al.:

In its core, linear regression amounts to orthogonal projection of $\mathbf y$ on (onto) $\mathbf X$, where $\mathbf y$ is the $n$-dimensional vector of observations of the dependent variable and $\mathbf X$ is the subspace spanned by the predictor vectors.
This is a very useful interpretation of linear regression.
Since $y$ is being projected on $X$, that is what I think when I hear that $y$ is "regressed on" $X$. From this point of view, it would make less sense to say that $X$ is regressed on $y$ or that $y$ is regressed "against" or "with" $X$.

Ideally I'm hoping that a proper explanation of why this terminology exists will help students remember it, and stop them from saying it the wrong way around.

As I said, I doubt that this is an explanation of why this terminology exists (perhaps only of why it persists?), but I am sure it can help students remember it.
A: As the target predicted outcome y depends on the predictor x, you can say that "is regressed on" means "is dependent on".
The word "regressed" is used instead of "dependent" because we want to emphasise that we are using a regression technique to represent this dependency between x and y.
So, this sentence "y is regressed on x" is the short format of:
Every predicted y shall "be dependent on" a value of x through a regression technique.
A: Personally, when it comes to explaining terminology, I find the definition of the term itself always helps, especially when explaining to students. The actual definition of the word regress is:
"return to a former or less developed state".
So one way to explain I guess would be the following:
"Thinking of the outcome as the fully developed state, we try to explain the outcome by using less developed states, i.e. the independent variables. Thus the outcome is regressed on the predictors."
Hope that helps.
