What is meant by "quenched" and "annealed" averages and how they differ from each other? I do not have a physics background but I have been reading about phase transition phenomena in computational problems and I cannot understand exactly what meaning these types of averages convey.
 A: There are two possible meaning to the words quenched and annealed:


*

*If we are talking about cooling, a system is quenched if it is cooled very rapidly, annealed if it is cooled slowly.

*If we are talking about disorder, a system has quenched disorder if it depends from random variables that don't evolve in time; it has annealed disorder if it depends on random variables that evolve in time.


I suspect that you are referring to the second meaning. A quenched average is therefore the average keeping the random variables fixed, while an annealed average is an average which is also carried out over all the possible values that the random variables can take.
A: Here I give the physics analogy, to help motivate the difference between the two averages discussed by @valerio92.
You start with a system that is in equilibrium with its environment. By equilibrium I mean that if the environment does not change, the system (statistically) won't either.
We are going to change the environment, to some fixed final state. We want to compute the change in the system. For example, we might have a sword that is currently white hot (being in equilibrium with the similarly-hot environment of the forge) and we now want to cool it.
There are two opposite limits we could do this. If we quench the system, we instantaneously change the environment to its final value by, for example, plunging the sword into ice water. The system has the same state that it did originally, but is now subject to a different environment.
If we anneal the system, we very gradually cool the environment, so that the system is in (quasi)equilibrium with it at all times. For example, we might very slowly reduce the temperature of the forge without removing the sword from it. 
