Let us try to produce the solution without applying brute force, similar to mgamer's answer (that did not actually use Mathematica).
Reduce[Mod[10^r - 1, 37] == 0, r, Integers]
(* -> C[1] \[Element] Integers && C[1] >= 0 && r == 3 C[1] *)
We see that the value of r can in fact be any nonnegative multiple of 3. The result sought is then obvious by inspection.
Supposing that we are not willing even to allow for a little interpretation of the above result, or if the outcome is somewhat more complicated, and we want Mathematica to produce the answer directly. Then, we can use Minimize (note that this finds a global optimum symbolically, and so is different from both NMinimize and FindMinimum) on the (minimally rearranged) output of Reduce to find the value of the undetermined constant:
Minimize[{3 C[1], C[1] >= 0}, C[1], Integers]
(* -> {0, {C[1] -> 0}} *)
Minimum r is thus seen to be 0 if we are only restricting it to nonnegative values. Or, if we want it to be strictly positive,
Minimize[{3 C[1], C[1] > 0}, C[1], Integers]
(* -> {3, {C[1] -> 1}} *)
Minimum r is 3.