Is it possible to get the order of inputs when "overloading" an orderless function?

Well, you can sort of do this, by creating something like a continuation. This requires playing games with the Stack, and I don't claim that it is robust, but it may represent some theoretical interest, particularly to those of us looking for ways to implement continuations in Mathematica. Here is the code (edit please note that I had to add Update[matrix] to address some improper behavior noted in the comments end edit):

ClearAll[matrix, inMatrix];
matrix /: HoldPattern[Times[pre___, a_matrix, post___]] :=
  (
      Update[matrix];
      ReleaseHold[NonCommutativeMultiply @@@ $stack]
  );
matrix[args__] /; ! TrueQ[inMatrix] :=
  Block[{inMatrix = True},
    Update[matrix];
    $stack = Stack[_][[-5]];
    matrix[args]]

It combines UpValues, Villegas-Gayley trick to redefine a function, and manipuations with Stack. What happens is that first, of course, the attributes of Times are applied, I can't fight that. Then, the DownValues of matrix are applied, and at this point I record the relevant part of the Stack. Then, UpValues of matrix are applied, and at that point I communicate the recorded part of the stack, where the attributes of Times weren't yet applied, and Times gets replaced with NonCommutativeMultiply, after which I re-evaluate this, as if it was not evaluated before. The Update sommand is used to prevent caching the values for the $stack, as this is inappropriate here and resulted in some erroneous behavior noted in the comments.

Here are some examples:

a = matrix["a"];
b = matrix["b"];

a*c*b

matrix[a]**c**matrix[b]

f[g[1 + c*a*d*b*e]]

f[g[1 + c ** matrix["a"] ** d ** matrix["b"] ** e]]

I would not probably recommend such tricks for serious use, it is just interesting that you can use them to divert evaluation sequence in ways which seem to be impossible otherwise.

there is a package called NCAlgebra I used some time ago to handle non-commutative variables (not just in matrix representation but also quaternions etc) in a multitude of situations.

http://www.math.ucsd.edu/~ncalg/

I think it would solve your problem as it defines its own substitution and expansion rules. You get the option to define a variable as non-commutative and then "do stuff" to it. In your example, and using this package

SetNonCommutative[A, B]

would define A, B to be treated as non-commutative symbols and the order in multiplication will be preserved.

As far as I know this cannot be made to work in the manner you show so long as the Orderless property of Times remains, because this property is applied before pattern rules are applied.

You can of course do things such as Blocking Times but I cannot think of a way to get (automatically) the behavior you desire without bad side effects.