Any probabilistic primality test will work, but GIMPS currently uses the first-time Fermat probable prime test with a very robust certificate [1] to filter almost all non-primes in advance.
It's called the "Lucas–Lehmer primality test". Without it, GIMPS probably wouldn't have found a single one of them in an acceptable amount of time. The one that was just discovered is HUGE. I had to write a program just to slow down the output enough to be able to appreciate its shear magnitude (it is still printing as I write this!).