The first theory on the conversion of heat into mechanical work is due to Nicolas Léonard Sadi Carnot in 1824. He was the first to realize correctly that the efficiency of the process depends on the difference of temperature between the hot and cold bodies.
Recognizing the significance of James Prescott Joule's work on the conservation of energy, Rudolf Clausius was the first to formulate the second law in 1850, in this form: heat does not spontaneously flow from cold to hot bodies. While common knowledge now, this was contrary to the caloric theory of heat popular at the time, which considered heat as a liquid. From there he was able to infer the law of Sadi Carnot and the definition of entropy (1865).
Established in the 19th century, the Kelvin-Planck statement of the second law of thermodynamics says, "It is impossible for any device that operates on a cycle to receive heat from a single reservoir and produce a net amount of work." This was shown to be equivalent to the statement of Clausius.
The second law of thermodynamics is a law about macroscopic irreversibility. Boltzmann first investigated the link with microscopic reversibility. In his H-theorem he gave an explanation, by means of statistical mechanics, for dilute gases in the zero density limit where the ideal gas equation of state holds. He derived the second law of thermodynamics not from mechanics alone, but also from the probability arguments. His idea was to write an equation of motion for the probability that a single particle has a particular position and momentum at a particular time. One of the terms in this equation accounts for how the single particle distribution changes through collisions of pairs of particles. This rate depends of the probability of pairs of particles. Boltzmann introduced the assumption of molecular chaos to reduce this pair probability to a product of single particle probabilities. From the resulting Boltzmann equation he derived his famous H-theorem, which implies that on average the entropy of an ideal gas can only increase.
The assumption of molecular chaos in fact violates time reversal symmetry. It assumes that particle momenta are uncorrelated before collisions. If you replace this assumption with "anti-molecular chaos," namely that particle momenta are uncorrelated after collision, then you can derive an anti-Boltzmann equation and an anti-H-Theorem which implies entropy decreases on average. Thus we see that in reality Boltzmann did not succeed in solving Loschmidt's paradox. The molecular chaos assumption is the key element that introduces the arrow of time.
The Ergodic hypothesis is also important for the Boltzmann approach. It says that, over long periods of time, the time spent in some region of the phase space of microstates with the same energy is proportional to the volume of this region, i.e. that all accessible microstates are equally probable over long period of time. Equivalently, it says that time average and average over the statistical ensemble are the same.
In 1871, James Clerk Maxwell proposed a thought experiment that challenged the second law. It is now called Maxwell's demon and is an example of the importance of observability in discussing the second law (see the article for details).
In quantum mechanics, the ergodicity approach can also be used. However, there is an alternative explanation, which involves Quantum collapse - it is a straightforward result that quantum measurement increases entropy of the ensemble. Thus, second law of thermodynamics is intimately related to quantum measurement theory and quantum collapse - and none of them is completely understood.