Why are the laws of thermodynamics "supreme among the laws of Nature"? Eddington wrote

The law that entropy always increases holds, I think, the supreme position among the laws of Nature. If someone points out to you that your pet theory of the universe is in disagreement with Maxwell's equations — then so much the worse for Maxwell's equations. If it is found to be contradicted by observation — well, these experimentalists do bungle things sometimes. But if your theory is found to be against the second law of thermodynamics I can give you no hope; there is nothing for it but to collapse in deepest humiliation.

and Einstein wrote

[classical thermodynamics] is the only physical theory of universal content which I am convinced will never be overthrown, within the framework of applicability of its basic concepts.

Why did they say that? Is it a very deep insight they had, or is it something one can be convinced of quite easily? Or even, is it trivial?
 A: The law of entropy is explained in terms of probability theory and this can in many cases be reduced to counting arguments. People believe that natural numbers work well, and whenever your theory has some notion of allowed states, you can look what statistical physics has to say about it. 
Thermodynamics is also generally the most large scale theory. That is it's is founded on only a few parameters, most notably energy $U(S,V)$, where $S$ is your entropy and $V$ is some macroscopic variable. History shows that people have always found a theory which describes the world in terms of quantities which let you set up an conservation-of-energy-law.
I'm unsure if Einstein means "not applicable anymore" by "overthrown". In a way all our theories which we test do fail - on the tiny scale - but the quotes are also not that recent. So how to read the expression "law of nature" from that quote? What does it mean for a theory used by engineers to be overthrown? As long as we are homo sapiens, I think all the practical theories we have are here to stay. In this sense, I would say I'm not sure if I'd not be more surprised if Maxwell laws were to fail in any sense I can interpret Eddington. On any macroscopic scale, we know mobile phones do in fact work and so what does it mean for electrodynamics to be wrong? I think the Church-Turing thesis has supreme position amongst "the laws of Nature", but then again, it might be not well posed and it might be not physics.
A: In addition to the other answers, I would like to add that Liouville's theorem, (volume in phase space is time-conserved) combined with some information analysis can foretell the existence of the second law of thermodynamics quite well.
If we adhere to an interprentation of Quantum Mechanics without "collapse" (since a collapse mechanic contraproves Liouville) we can even derive it direcly from the most base physics known.
The reasoning goes like this: Liouvilles theorem says phase space volume is conserved. Unfortunately we have finite reasoning capacity, so we blur our eyes a bit in order to not be overwhelmed, losing information in the process.

This little simulation quickly grows incredibly swirly, in fact I can't even keep track of it. Can you?
The second law of thermodynamics is, however, only meaningful if we try to do informational analysis of it. In the absence of an information system with finite capacity for analysis and measurement, it is quite meaningless.
A: Einstein is being much more profound and subtle than Eddington, but even Eddington's quote has been misunderstood.  Eddington is not saying that the Second Law of Thermodynamics can never be violated, in fact, in other passages of his, which I have posted on other places on this site, he explicitly says it is possible.  No.  What Eddington is saying is that if your theory qua theory proves that as a rule entropy need not increase, then there is no hope for you.  In very exceptional or rare cases which, btw, won't be reproducible by other experimenters since they are freakish, Eddington admits the Second Law can be Violated.
Einstein is being more interesting.  Note well his caginess in qualifying his statement: "within the framework of the applicability of its basic concepts."  Obviously he means at least "assuming it is within the realm of validity of the approximations it makes", e.g., we have to be talking about macroscopic bodies, macroscopic properties, and macroscopic variables.  Not Szilard engines.  But he means more, and in two interesting ways.  
A.  As anna v. points out in a comment somewhere, Thermodynamics or Stat Mech are mathematical theories which make certain idealisations from the real world.  I rarely agree with the exact way she phrases things, but here Max Planck in his very old book on
Thermodynamics makes explicit one of the idealisations made by Thermodynamics, so that 
its results are only approximations:  we always assume that the dynamical system passes 
from its current state to the most probable macro-state which it can pass to.  The Laws 
of Thermodynamics, indeed, its entire mathematical structure, rest on this assumption, 
according to Planck.  So Einstein is saying that provided this assumption holds true, 
the conclusions of Thermodynamics will never be overthrown.  And Einstein was certain
that the conclusions of Quantum Mechanics would be overthrown, even within its own 
realm, by a more complete deterministic theory with hidden variables.  So he is 
implicitly contrasting Thermodynamics with that and making Thermodynamics more fundamental
than Quantum Mechanics.  This is saying a lot more than just that the experimental observations which, to date, support Thermodynamics, will never be contradicted in the 
future.
B. Einstein, I feel sure (I guess that is a kind of disclaimer...the more someone uses words like "sure", the less they ....)  was also contrasting Thermodynamics with, e.g.,
the Newtonian theory of gravity.  People are fond of saying that the Newtonian theory
retains its validity as a good approximation.  But Einstein is asserting that Thermodynamics is much more than just a good approximation.  Newtonian gravity is a bad
approximation to events near black holes, and even the principle of the constancy of 
the speed of light (Special Relativity) is a bad approximation near a black hole.  Einstein is asserting that the logical structure of Thermodynamics will be retained in 
all future physical theories, no matter what new forces are discovered, and that
it can and will be erected on top of whatever new fundamental physics comes along, substantially unchanged.  The new fundamental physics will find the new places where the 
old fundamental physics is a bad approximation, but Thermodynamics will remain valid even 
in those new places.  For example, it remains valid for black holes.
These are not necessarily my own opinions.
A: I think the name of Josiah Willard Gibbs ought to appear somewhere on this page because I think he deserves much of the credit for formulating these "laws" into the form we recognize. Also, I was taught that a "law of nature" was an empirical rule formulated by observation and induction. If you consider the laws of thermodynamics as "supreme" that might be justifiable because (1) no experimental evidence has ever been found that disproves these "laws" and (2) they were the product of a genius.
A: Your statement is somewhat subjective, so really can only be answered by trying to put together what thoughts about physics such great physicists were thinking when they made their statements.
Firstly, the laws of thermodynamics have very different origins and putative theoretical justifications and indeed the Eddington quote only talks about the second.
I have heard the Eddington quote, but I don't know a lot about the man because I'm afraid "I've never really forgiven him" for the following exchange:

“Asked in 1919 whether it was true that only three people in the world understood the theory of general relativity, [Eddington] allegedly replied: 'Who's the third?” [1]

and so am wont to take him with a grain of salt (and, probably unjustifiably, neglected to find much out about him). However, James Clerk Maxwell thought something very like this about the Second Law and what he was getting at was that it was an emergent phenomenon from the laws of large numbers in probability theory, and a weak form of it can be derived from very basic assumptions quite independent of the details of the physical laws steering a system's micro-constituents. First of all, consider the simple binomial probability distribution for, say, sampling of red balls from a population which is, say, 43% made up of red balls. If you take a sample of ten, then you'll most likely to get four or five red ones, but the likelihood of getting two or three or eight or nine is also very great. The simple number 0.43 does not tell you very much about the character of the kinds of samples you'll get. However, if we take one million balls, the number of red ones will be 430 000 to within a very small proportion error, roughly of the order of $1/\sqrt{N}$, which is about 0.001 here. So even though the absolute number of red balls will vary quite widely from sample to sample, the simple statement "43% are red" characterises the sample extremely well. The binomial distribution gets "pointier and pointier" such that, even though the probability of getting exactly 43% red balls is fantastically tiny, almost all the possible arrangements, i.e. samples, look almost exactly like a sample with 43% red balls. The probability of getting, say, 420 000 or fewer, or 440 000 or more red balls out of a sample of one million is so small (roughly $10^{-90}$ !) that it can be neglected for all practical purposes:
A large sample looks almost exactly like the statistically expected sample, and this statement gets more and more accurate as the sample gets bigger and bigger
So too it is for, say, the derivation of the Boltzmann distribution from the microcanonical ensemble on the Wikipedia page "Maxwell-Boltzmann Statistics". You have two Lagrange multipliers in this one, but the essential idea is almost exactly the same as the binomial distribution I've just talked about. You find out the most likely arrangement, given the basic assumption that all possible arrangements are equally likely. Stirling's formula works exactly the same as it does when you approximate the binomial distribution for large samples. What the Wikipedia derivation (as do I think all of the ones I've seen in physics texts) glosses over is this following powerful idea: 
The distribution gets "pointier and pointier" such that almost all of the arrangements look very like the maximum likelihood one. The probability of finding an arrangement significantly different in macroscopic character from the maximum likelihood one becomes vanishing in the thermodynamic limit of a large number of particles.
So then, in any system of a large number of particles there are states that look almost exactly like the maximum likelihood macrostate and there is almost nothing else.
Therefore, if for some reason, a system finds itself in a state that is significantly different from the maximum likelihood one, then it will almost certainly, through any random walk in its phase space, reach a state that is almost the same in macroscopic character as the maximum likelihood one. (The reason for the unlikely beginning state might be, for example, that one of we monkeys in white coats has created a system comprising a pellet of native sodium in a beaker of water. Kaboom!) This, of course, is a "laboratory form" of the second law of thermodynamics. At the level of universes, though, the grounding of the second law becomes much more experimental in nature (see the Physics SE question How do you prove the second law of the dynamics from statistical mechanics? and also my answer here), but the stunningly fundamental and simple reasons for its holding in its weak form as I talked about above give physicists deep reasons for believing that the second law is generally true. 
But note in passing that my arguments do not work in the small. Entropy can and does fluctuate wildly in both directions for systems comprising small numbers of particles, see the review paper:

Sevick, E. M.; Prabhakar, R.; Williams, Stephen R.; Bernhardt, Debra Joy, "Fluctuation Theorems", Annual Rev. of Phys. Chem., 59, pp. 603-633, arXiv:0709.3888.

You can also see the Wikipedia page on the fluctuation theorem.
The first law, to wit, conservation of energy, is very different in character and grounding. Again, it is experimentally proven: it has been found in countless experiments over roughly two hundred years that systems behave as though they have a certain "budget" of work that they can do; it doesn't matter how you spend that budget, but if you tally up the work that can be done by the system in the right way (i.e. as $\int_\Gamma \vec{F}\cdot{\rm d}\vec{s}$, or $\int_0^T V(t)I(t){\rm d}t$ in an electrical circuit and so on), then the amount of work that can be done will always be the same. There is also theoretical motivation for energy conservation: the idea of time shift invariance of physical laws. That is, physical laws must give foretell the same outcomes after we arbitrarily shift the time coordinate. Physics cannot be dependent on what we humans choose to be the $t=0$ time. Through Noether's theorem, we find that this implies for physical systems with a Lagrangian description with no explicit time dependence that the total energy must be conserved.
It is ironic, therefore, that Einstein made the comment, given that his general relativity is one theory, wherein this time shift invariance breaks down. Global time cannot be defined on cosmological scales for a spacetime manifold fulfilling general relativity so our time shift invariance argument cannot be applied. Physicists therefore do not believe that conservation of energy holds for the whole universe (although there is still local conservation of energy in general relativity). I'm sure Einstein was aware of this flaw in his general statement, so, although first law has very solid grounds in almost any practical case we wish to consider, it seems probably Einstein was talking about the second law in particular.
A: Four laws of thermodynamics:


*

*Conservation of energy. Makes sense, if we lose energy it must go somewhere, we may not know where but it stands to reason that it must go somewhere. If we gain energy we must gain it from somewhere again.

*Entropy only increases. There are obviously way more ways for a system to be disordered than there are ways for it to be ordered. (think of your room. an ordered state means your books are confined to the desk and you cloths to the closet. a disordered state has endless possibilities). This means that the probability of a system moving from a disordered state to an ordered one is small enough, that if we were to observe it we can safely assume that some energy is being poured into the system directing it. (ex: you cleaning your room).

*"The entropy of a system approaches a constant value as the temperature approaches zero"
at absolute zero there is no energy, and if there is no energy nothing can change its state. since any difference between the elements within the system would have caused an exchange and therefore energy. We can infer that that all elements are equal.

*This one seems to say that if $a=c$, and $b=c$, then we conclude that $a=b$.
I am not a physicist (which is obvious by my explanation) but these strike my as very basic intuitive principles. They are almost on par with logic and algebraic principles.
A: As a computer scientist who deeply respects the beautiful and astonishing relativistic and quantum frameworks that emerged about a century ago, I would only like to note that I strongly agree that thermodynamics defines the deepest levels of reality. Why? First you must understand what information is, since entropic definitions by themselves only tell you how to find and measure it, not what it is. In terms of space, time, momentum, and matter, a single bit of information is the choice of one quantum path over another equally likely one. When applied at the level of atoms and particles, the result is a tapestry of choices that quickly becomes nearly infinite in complexity. From our large-scale view, this fine-grained statistical tapestry becomes the fabric of thermodynamic entropy -- and through that, the foundation of historical reality. It is this thermodynamic fabric of interwoven choices that transforms the boringly symmetric infinity of universes of quantum mechanics into a singular and historical universe in which conversations like this one can exist and have meaning. In short, thermodynamics is profound because it defines the ongoing dance between what could have been and what has actually come to be.
A: I can't be sure why they said that, because I don't have mindreading powers.
But a strong reason why thermodynamics has a privileged position is that it's a macroscopic theory. This means that all the magnitudes you deal with can be easily measured, so you don't have to worry about the messy microscopic details. Even if you don't know what's happening at a fundamental level, you can describe your system with a couple of thermodynamical variables.
Whether it's a black hole or a quantum system, you only need to measure entropy, temperature... The underlying theory must always agree with thermodynamical observations.
A: There is no such law that "entropy increases", there is a widely accepted formulation of one part of the so-called 2nd law of thermostatics that when moving from one equilibrium state to another the entropy of an isolated system cannot decrease. There are several similar not completely equivalent formulations of the same but it is about isolated systems between equilibrium states. This is the non-controversial part of the 2nd law about which nobody argues. Compare this with the arguments and confusion one encounters the moment the system is not isolated and/or non-equilibrium.Say it exchanges heat, for example: what is q and whose T is in q/T, what is a reversible vs. irreversible process ? 
The formulation of the 2nd law for non-equilibrium states and processes connecting them has never been fully resolved in the 150 years of development of the subject since the time of Clausius and Kelvin. Even the concept of what is to be meant by a "state" is controversial. I think Truesdell said that there were as many "2nd laws" as physicists... Some physicists whom Truesdell dismissively called "dis-equilibrated" deny that entropy can even be defined for non-equilibrium states. Others like Bridgman, Eckart, Coleman, Noll, Truesdell, etc., don't care and define entropy for almost any macroscopical state and formulate the 2nd law as an inequality between rates acting as restriction on possible constitutive relations - this is the so-called "rational thermodynamics". There are other schools of thermodyanamics, mostly using quasi-linear and near equilibrium formulations, such as the so-called Belgian school (Prigogine, Glansdorff, etc.). Despite its ancientness this subject is not closed at all. 
A: The law that entropy always increases is a mathematical theorem, it is not a law of physics.
Postscript:
A law of physics is an hypothesis about nature. It is considered valid until it is contradicted by an experiment. In that case the law is said to be falsified.
A law of physics can not be proved; but it can be disproved (by experiments).
The theory of relativity is accepted because (and so long as) it has never been contradicted by an experiment.
The law that entropy always increases is different. It can actually be proved, as any mathematical theorem. It follows from the (mundane) observation that a system has the highest probability being in the state with the highest degree or freedom (or the most permutations).
I suppose it is considered a law of physics mainly for historical reasons...
