In the case of

Select[{1, 2, 3, 4, 5}, # > xx &] /. xx -> 2

the

 Select[{1, 2, 3, 4, 5}, # > xx &]

is evaluated first (it returns {} obviously) and then the replacement rule is applied to the result (again returning {}). The standard Mathematica evaluation sequence is to evaluate expressions from the inside out of the FullForm of the expression.

FullForm[Hold[Select[{1, 2, 3, 4, 5}, # > xx &] /. xx -> 2]]

returns

Hold[ReplaceAll[
  Select[List[1, 2, 3, 4, 5], Function[Greater[Slot[1], xx]]], 
  Rule[xx, 2]]]

and this shows that the ReplaceAll in this case is the outermost function--everything inside of it is evaluated first.

In contrast your second example,

FullForm[Hold[Select[{1, 2, 3, 4, 5}, # > xx & /. xx -> 2]]]

which returns

Hold[Select[List[1,2,3,4,5],ReplaceAll[Function[Greater[Slot[1],xx]],Rule[xx,2]]]]

has the replacement rule being applied within the Select's second argument.

I hope this helps...