The name discriminative leads to some inherent definitions that I don't think are true. When first told of discriminative models, intuition says "It is a model that improves training accuracy between different classes by focusing on features that discriminate each class from each other class". I don't think that's true though.
Why are they called 'discriminative'? And how off-the-mark is my above statement?
I think your intuition isn't too far off the mark. As Wayne wrote, the major distinction is discriminative vs generative (sometimes called 'informative' instead)
Discriminative models just want to find a way to separate observations into classes; they want to sort the As from the Bs, Cs, and Ds, but don't particularly care about what features make an 'A' an 'A' as opposed to a B. In contrast, a generative model tries to capture how the observations were (or could have been) generated. To classify a specific observation, it then asks "given our model for each of the classes, which one is most likely to have generated this data?"
You can think of a discriminative model as capturing the differences between classes (but not any information about the classes themselves), while a generative model captures information about each class, but not their differences.
For classification, I think discriminative models are often more efficient (e.g., see this "shoot-out" http://robotics.stanford.edu/~ang/papers/nips01-discriminativegenerative.pdf) but a generative model might have more applications, particularly if you want to discover something about the classes themselves.
tl;dr: Discriminative models "discriminate" BETWEEN classes. Generative models represent each class.
Discriminative classifiers construct from training data the optimal (w.r.t some choice of loss function) decision boundary between classes. A query point is then classified according to which side of the decision boundary it lies on. They are called discriminative because that is what they do, they discriminate between classes.
Generative classifiers attempt to model the unknown data distribution, i.e. the distributions of the classes. A query point is then classified according to which class distribution it is most representative of.
Now consider the case where one has many training observations: Because in the discriminative case the optimal boundary is found, as the number of observations increases discriminative classifiers are provably convergent to the best possible classifier.
On the other hand in the generative case a data distribution is estimated, and the choice of model distribution may not (in fact, most likely will not) exactly match the true distribution of the data. Clearly a generative classifier can only be optimal when the model distribution matches the true distribution of the data, and this is the sense in which discriminative classifiers are often said to be superior to generative classifiers; the asymptotic loss of a generative classifier is typically higher than that of a discriminative classifier.
BTW the paper by Andrew Ng linked to by @Matt Krause is very well known, and certainly worth a read. He examines the effect of training set size and demonstrates that generative classifiers can converge more quickly to their (higher) asymptotic loss, i.e. can be better when there is little training data, but in the long run discriminative classifiers overtake their performance.
I believe it's clearest when you understand that discriminative models are in contrast to generative models. From a generative model, you can generate (simulate) values for any variable in the model. A discriminative model cannot do this, but can only discriminate (classify) between various observations.
As the Wikipedia definition of generative model says:
a generative model is a full probabilistic model of all variables, whereas a discriminative model provides a model only for the target variable(s) conditional on the observed variables
I'm not sure if I'm correct, but I think of it as: a generative model is an attempt to model a system, with many possible uses, while a discriminative model is more of a black box which is good at sorting observations into classes.
A famous quote by Vapnik in favor of discriminative modeling for classification is: "one should solve the classification problem directly and never solve a more general problem as an intermediate step".
