If I create two workflow rules, the first being
Whenever a case is opened, set Example Case Field to A
and the second being
Whenever a case is opened, set Example Case Field to B
how does Salesforce determine the order of execution?
The order of execution is indeterminate. Technically speaking, the current implementation seems to be that the workflow rule created last will take precedence, but you must not depend on that behavior.
If you create two rules that both update the same field, the result will be one of the two updates, but you will not be able to determine which value will win ahead of time. One field update will overwrite the results of the other. You should avoid creating rules that may simultaneously update the same field.
I could be wrong, but I don't think the documentation defines an order in which workflow rules are evaluated, nor the order in which field updates are applied (which is the real issue here).
I'd treat it as non-deterministic, and avoid having multiple workflow rules (on one object) that have the same evaluation criteria.
If you need to set different values on a common field under similar circumstances (that is to say, if workflow B being triggered means that workflow A will also always be triggered), then that is not a situation that workflow is well-suited to handle. At that point, triggers start to become necessary.