What sets a "Law" apart from a "Rule" or a "Principle"?
A theory is a collection of concepts, laws, and equations in science that is meant to explain some particular subset of observations. It's also used for theories describing gedanken worlds that differ from ours. There is also a related word "model" that differs by a theory by being really specific while a "theory" may leave some details adjustable, and "framework" which is on the contrary less specific than a theory and fully determines the general methods, and type of objects and arguments that are allowed in research. The boundary between the terms is not quite sharply delineated.
A theorem is a mathematical proposition, usually a hard one to prove or disprove, and usually a far-reaching and general enough, that has been proven to hold by rigorous mathematical methods. A lemma is a less important version of a theorem, usually one that is used as a step to prove full-fledged theorems.
"A rule" is usually used for some prescriptions that should be memorized and that chooses the right answer from a usually small list of possibilities. In particular, there are right hand rules that determine the sign of some quantities and/or its relationship to directions in space (this direction or opposite direction). Some of the rules define conventions – claims that could have also been chosen in the opposite way but people must understand each other so they agreed to use one particular sign etc. Hund's rules determine which angular momentum is chosen – again, the number of candidates is usually limited.
"A law" is a more substantive insight about Nature, a building block of our understand how Nature (or the society) works. It may be equivalent to one equation, one identity for continuous quantities, like Coulomb's law for the attraction or Ohm's law $U=RI$ etc. How Nature works is described by the "laws of physics".
"A principle" is more general than a law and it is usually a statement of a general type or a philosophy or a condition that good laws (explained in the previous paragraph) are supposed to satisfy. A principle is therefore an extra criterion that has been induced from the observations and the known laws and that is imposed on the new candidate laws. The principle of relativity is an example. Principles usually require more verbal, words-based descriptions to be fully formulated, as opposed to a single particular equation that may define a "law".
There is no consistent usage of these words among scientists.
Usually, when someone says "law" or "principle", they are referring to a general idea that has been found to apply to many different situations, but not always. More speculative ideas are generally called theories, but use of the word "theory" does not always mean that an idea is speculative.
All I can say for certain is that you should not make assumptions about whether an idea is speculative or confirmed, general or specific, etc. based only on whether it is called a theory, law, rule, principle, or something else.
In case you ever have to answer this question in a hurry or are explaining it to someone that might not be able to follow Lubos' answer fully. Let me present a shorter, root version.
A scientific Law is a statement of observations. That is all. This statement may come with equations, but it is always "It is observed in nature that (Given observable) follows (Given pattern/equations) subject to (Given conditions)".
A theory is a statement that attempts to explain observations. Again, that is all. It is not necessary that these observations have been made; a theory may explain observations that have not been made - this is called a prediction. A prediction that is shown to be correct is confirmed and the original theory becomes a regular explanation of the new observations. A theory is usually based on mathematical or logical premises that are easily acceptable. It is possible for these premises to include other Laws or theories. It usually comes in the form of "We believe (mathematically or due to lack of evidence to the contrary) that (Given Law) applies to nature because (Given premises) implies (Given intermediary reasoning/mathematics/hypotheticals) would be true and, thus, we should observe (Given Law)".
A Rule is a statement of conventions. Lubos mentioned the Right-Hand-Rule, an excellent example. Rules describes the proper way to perform a task. They usually take the form, "In order to (Given task) and be able to reconcile (task's results) with the understanding of your peers, you should (Given Rule)". A rule is unique because two completely isolated societies with the same level of scientific understanding should have the same Laws and theories, but they may have entirely different rules.
A Principle (in physics) is a statement of the limits of intrinsic natural properties. It is different from a Law because it is not a statement of one type of observation but rather a statement of the patterns governing Laws and Theories. A Principle is a powerful statement; it can never be ignored; there are absolutely no exceptions to a Principle. A Rule can be ignored easily by changing conventions. A Theory can have exceptions, which often may indicate that the theory is incomplete but they won't necessarily disprove it. A Law cannot be ignored or have exceptions within the limits established by the Principles of Nature (remember, they are statements of nature's limits). Outside of these limits, all Laws are subject to the "Law of Exceptions" - every law has exceptions, no exceptions. For example, consider the Heisenberg Uncertainty Principle. It describes the limits on the amount of information one can have about something. Within this limit, the Laws are immutable, however, if you consider (for example) distances or time scales less than the Heisenberg limit, processes that violate the Law of Conservation of Energy are allowed. It is only Principles that may never have exceptions. A Principle is usually of the form "All natural systems are subject to (Given limits) with respect to (Given intrinsic property)".
The definition I gave for a Principle might seem a bit iffy. Let me clarify, an intrinsic natural property is not a direct observable; examples are the amount of information about a system, the Action of a process, etc. To state the principle of least action in the form I identified; "All natural systems are subject to (a minimization) with respect to (the Action of that system)".
Having said all this, I realize I promised a brief answer..... It seems I failed at that. However, when explaining to someone else, it should suffice to take the first sentence of each of the 4 defining paragraphs. Hope this helps.