As far as I understand it, once a subexpression gets replaced, it can't get replaced again. Try this:
a*b /. {a -> a, a -> 1, b -> c}
resulting in
a*c
The first replacement just replaces a with a, but since that expression has already been changed, it is ignored after that. So the Rule a -> 1 is only applied to other parts of the expression (in this case the b), and those other parts don't depend on a, so nothing changes. Finally, b gets replaced with c. (By the way, in somewhat-advanced Mathematica programming, this fact can be taken advantage of in many clever ways. Here is an example by Mr. Wizard, provided in the comments.)
So you're kind of right and kind of not. The Rules are applied sequentially, but the rules are not applied to the new expressions resulting from previous replacements.
Here's another interesting example:
a b c /. {a -> b, b -> c, c -> d}
% /. {a -> b, b -> c, c -> d}
% /. {a -> b, b -> c, c -> d}
(* b c d *)
(* c d^2 *)
(* d^3 *)
In the first case, the a instance is replaced by b, but it is not in turn replaced by c. However, the original b is replaced by c. And so on. To do all of them at once, use ReplaceRepeated:
a b c //. {a -> b, b -> c, c -> d}
(* d^3 *)
(Be careful of this one, because it can run into infinite recursions.) For completeness, note that ReplaceRepeated does not act the same as a sequence of ReplaceAlls if the list of Rules are different:
a b c //. {a -> b, c -> d, b -> c}
a b c /. {a -> b} /. {c -> d} /. {b -> c}
(* d^3 *)
(* c^2 d*)
Finally, as noted by Daniel Lichtblau in a comment, if you do want to apply the two rules to get different expressions, do this:
2 x + y /. {{x -> 3}, {x -> 4}}
(* {6 + y, 8 + y} *)
Alternatively, do
2 x + y /. # &/@ {x -> 3, x -> 4}
or
2 x + y /. List/@{x -> 3, x -> 4}
