How can I get the While function to evaluate two conditions simultaneously?

You want to use Or rather than And. Then you are printing are all of the failures and the final success.

Clear["Global`*"]

a = 1; b = 1; n = 1;

SeedRandom[12]

While[a < 6 || b < 6, a = RandomInteger[10]; b = RandomInteger[10]; 
 Print["Try ", n++, ": a = ", a, ", b = ", b]]

(* Try 1: a = 2, b = 4

Try 2: a = 0, b = 10

Try 3: a = 1, b = 9

Try 4: a = 7, b = 3

Try 5: a = 1, b = 10

Try 6: a = 7, b = 0

Try 7: a = 9, b = 5

Try 8: a = 4, b = 6

Try 9: a = 7, b = 2

Try 10: a = 8, b = 5

Try 11: a = 4, b = 7

Try 12: a = 8, b = 8 *)

While works when condition True. Stop condition is a > 6 && b > 6. So working condition should be Not[a > 6 && b > 6]

a = 1; b = 1;
While[a < 6 || b < 6,
  Print[a, "   ", b];
  If[n < 6, a++, b++];
 ]

Here are a couple of solutions that use the functional approach:

(* METHOD 1 *)

ClearAll[f1];
f1[{x_, y_}] /; Or[x < 6, y < 6] := (
    Print[{x, y}];
    f1[{RandomInteger[{0, 9}], RandomInteger[{0, 9}]}]
);
f1[{x_, y_}] := {x, y};

(*
f1[{0, 0}]
{0, 0}
{6, 4}
{3, 9}
{5, 5}
{8, 9}
*)

(* METHOD 2 *)

ClearAll[f2];
f2 = ReplaceRepeated[{x_, y_} /; Or[x < 6, y < 6] :> (
    Print[{x, y}];
    {RandomInteger[{0, 9}], RandomInteger[{0, 9}]}
)];

(*
f2[{0, 0}]
{0, 0}
{1, 5}
{4, 2}
{1, 7}
{7, 4}
{7, 7}
*)

Side note: Yes, I am aware that the presence of the Print statements makes the functions non-functional.