What is the difference between classical correlation and quantum correlation? What is the difference between classical correlation and quantum correlation?
 A: Correlation is first and foremost a term from statistics. Given a system that consists of two (or more parts), it quantifies how much I can predict about the second system if I have knowledge of the first in comparison to how much I can predict about the second system without that knowledge. 
For instance, if I have a bag of pieces of paper printed with either the combination 00 or 11 with equal probability and I randomly pick a piece and only look at one of the two numbers, then I know the other number perfectly, while if I don't look at the piece of paper at all, I can only guess and will be wrong 50% of the time. Clearly, knowing part of the system helps me a lot.
Now let's consider physics: In classical mechanics, you can also consider statistical systems (such as many planets in a system or a bunch of particles in a box) and ask questions about that system (for example: what's the temperature of the box? How many particles will be faster than some speed x? How many particles will be in one half of the system when I measure?). If you divide your system, you have the same situation as above and you can ask whether the knowledge of part of the system lets you infer something about the other part of that system. Since we have a system in the theory of classical mechanics, those could be called "classical correlations". 
With quantum mechanics, you have a different theory of how our world works which possesses a different mathematical description. In particular, all quantum mechanical systems are statistical systems and you can ask a bunch of different questions about them - for example the spin of a particle in a particular direction, etc. If you take a system consisting of two (or more) parts, you can once again ask some questions and check how well you can predict the outcome of the second half of the system knowing the first. Your results will once again depend on the correlation of this system and you would call this "quantum correlation". 
It's that simple. But there is a caveat:
Often, you will hear "quantum vs. classical correlations". What people mean by that is that in quantum mechanics, you can have degrees of correlation that are impossible to achieve if you model the system with classical mechanics. In a sense, those correlations are "purely quantum mechanical". Some people say that systems show "quantum correlations" only if they cannot be modelled by classical mechanics, otherwise they show "classical correlations". In other words: Given the terminology above, classical correlations are what I called classical correlations and quantum correlations are what I called quantum correlations minus those where I can get the same outcome using classical mechanics (for instance: I can model a quantum system with two parts where I can make a measurement - call it "color" - and the outcome on both parts is completely random: knowing one part doesn't tell me anything about the other part. Obviously, I would get the same outcome if I modelled this system with an urn of infinitely many billard balls with two colours each occuring with 50% probability and I draw two balls and try to predict the colour of the second ball knowing the colour of the first). 
This terminology also makes sense, because the correlations that are not classical are mostly the interesting types of correlation, because they tell us that for such systems, classical mechanics is indeed the wrong theory and we must take quantum mechanics to describe it accurately. If you want to learn more about that, I suggest you read about Bell inequalites.
Last but not least:
You can also construct mathematical systems that allow for even higher degrees of correlation (in terms of predictiveness) than quantum mechanics, but we have not yet found any physical system with such properties. In other words, quantum mechanics isn't really that special with regards to correlations.
A: It feels like the answer was that "any correlation that is not classical is quantum". That is correct but it doesn't really explain where the quantum nature comes from and what it really is. In quantum mechanics, as opposed to classical mechanics, the outcome of an observable doesn't have to always be the same value. There is in fact a set of possible values, playing the role of the eigenvalues of the observable which becomes a hermitian matrix. That is where the actual difference between classical and quantum lies. In classical physics any observable has one and only one outcome, fluctuations around it may result in our devices not being accurate enough, errors, lack of curiosity, etc. but finally, in classical physics there is always one single possible outcome for any question. This is not so in quantum mechanics, where, even with no perturbation on the system, we may one time get the result given by one eigenvalue, and another time by another eigenvalue. This is what it means that quantum mechanics is fundamentally probabilistic, and obviously, if we take a system described by an eigenfunction of such an observable, and separate it into two subsystems, there will be way more correlation if we have a lot of possible outcomes that are described by the eigenvalue of a matrix. Such a system is described by eigenfunctions that belong to a Hilbert space that can be split according to our division into two subsystems, but it's far from splitting the states describing the whole system in the same way.
So, extra correlation in quantum mechanics comes ultimately from the nature of observables in quantum mechanics which is quite different from the nature of observables in classical mechanics...
