Summarizing what Cole says for my own understanding: By methods which he doesn't make clear to me, Cole found solutions to $x^2 \equiv a \bmod N$ for many small values of $a$ and convinced himself (but not rigorously) that many other $a$ were not achievable. This gave many congruence conditions on possible divisors of $N$. In this manner, he was rapidly able to filter the integers up to $16$ million down to just a few trial divisors, none of which worked. (Note that it is okay if he winds up trying some non-prime divisors in the process.)

At this point, he used his data in a different way. Suppose that $N=pq$ and look at one of his small values of $a$, for example $a=-7$. Since he knew $-7$ was square modulo $N$, we deduce that $p$ and $q$ are each $ 1$ , $2$ or $4 \bmod 7$ and, since $2^{67}-1 \equiv 1 \bmod 7$, we get that $(p,q)$ is $(1,1)$, $(2,4)$ or $(4,2) \bmod 7$. This means that $(p+q)/2 \equiv 1$ or $3 \bmod 7$. In this way, he obtained many modular conditions on $(p+q)/2$, giving a few possibilities. For each possibility $x$, he checked whether $x^2-N$ was square. When he tried the right option, he had $x^2-N = ((p+q)/2)^2 - N = ((p-q)/2)^2$ and won.