Q:

Why Infinity /. _?(#  < 6 &) -> 0 replaces Infinity with ComplexInfinity? 

Suppose I define a matrix:
mat = {
    {Infinity, 4, 9},
    {6, Infinity, 10},
    {8, 9, Infinity}
   };

Now I want to replace all values smaller than 6 with 0,
mat /. _?(#  < 6 &) -> 0

However, that ends up replacing Infinity with ComplexInfinity, which is undesired.  Why is this happening? 
Update: A simpler example, as suggested by kguler in the comments, is:
Infinity /. _?(#  < 6 &) -> 0

which returns ComplexInfinity. 

A:

A few things are happening in there.   
First, Infinity is being replaced by DirectedInfinity[1] in order to perform the comparison.  In fact Infinity is just an abbreviation of DirectedInfinity[1].  You can see it by doing:
Infinity // FullForm
(* DirectedInfinity[1] *)

Next, the comparison takes place.  It's done in the same way Mathematica always does, like in:
h[1] /. _?(#  < 6 &) -> 0
(* h[0] *)

But in your case the head h is DirectedInfinity.  So your result is 
(* DirectedInfinity[0] *)

Now, that is a non-oriented infinity, exactly the same as ComplexInfinity.  Just try it:
DirectedInfinity[0]
(* ComplexInfinity *)

And that's it. 

A:

At some point, someone might want to write a good question about how to debug patterns that do not work as (naively) expected.   When I was first learning about patterns, I found it frustrating and confusing.   Now, I wonder what was the big deal.   It can still be difficult to find the right pattern, just as there are difficult problems in every area.   The gap in my understanding between then and now suggests there are things to be learned and things that could be explained.   However, my understanding has not advanced to the point that I have a systematic and foolproof method of what to do when a pattern does not match what you intended.   I can share one or two pretty good principles, but beyond that, it's like a lot of problem solving, I stab this way or that until I realize how stupid I've been or I have one of those rare moments we've all had when something rather clever actually occurs to us. 
Two pretty good principles:

Examine the FullForm.   A pattern, when it matches, matches an expression in its full form.  As has been pointed out FullForm[Infinity] shows DirectedInfinity[1].   There are three expressions that might possibly match any pattern, the whole expression, the head DirectedInfinity, and the argument 1. 
Isolate the problem.   Full forms are hard to read.   The smaller you can make an expression that exhibits the problem, the better.   As has been pointed out, the problem in the present question is with Infinity and not with the entire matrix. 

Some tools
There are some things you can do to understand what a pattern is matching.   Other users may use other methods, quite possibly better ones. 
Position can show which parts of an expression matches a pattern. 
mat // FullForm
Position[mat, _?(#  < 6 &)]

Cases will extract expressions that match.   The result might or might not be enlightening. 
Cases[mat, _?(#  < 6 &), Infinity]
(*  {1, 4, 1, 1}  *)

One problem with Cases is that the returned values are evaluated (see below for further consideration of evaluation).   Mr.Wizard has written a function heldCases that will return the matches inside HoldComplete.   The syntax is like Cases:
heldCases[mat, _?(#  < 6 &), Infinity]
(*  HoldComplete[1, 4, 1, 1]  *)

Print can print useful information sometimes.   The following shows that the 1 matches
Infinity // FullForm
Infinity /. _?(( Print[{FullForm@#, # < 6}]; # < 6) &) -> 0

Evaluation can be triggered by replacement.   For instance, in the present case, DirectedInfinity[0] evaluates to DirectedInfinity[].   This is potentially confusing, since in the resulting output, it does not appear that something was replaced by 0 as specified by the rule.   Controlling evaluation so that some things happen and others do not is another area of Mathematica that has been difficult for me.   In the present case we can use Hold.   I write Hold @@ {mat} so that mat will evaluate and then be held.   The replacements will happen, but the results are not evaluated. 
mat // FullForm
Hold @@ {mat} /. match_?(#  < 6 &) -> 0 // FullForm

Highlighting.  I hardly ever do this, but tracking down the parts returned by Position can be tedious.   The use of HoldForm may be overly cautious on my part. 
Position[heldexpr = HoldForm @@ {mat}, _?(#  < 6 &)]
ReplacePart[heldexpr, # -> Style[Extract[heldexpr, #, HoldForm], Red] & /@ %]

Another way to show where the matches are is to use the positions to extract the parent expression of the expression that matches.   This can be more useful than the use of Cases above:
Position[heldexpr = HoldForm @@ {mat}, _?(#  < 6 &)]
Extract[heldexpr, Most /@ %, HoldForm@*FullForm]

Note from the position information, it is the second element of List[DirectedInfinity[1], 4, 9] that matches the pattern. 

Well that is more than enough for the present case.   Perhaps some of the techniques will be helpful to others who are struggling to learn how pattern matching works.