Here's an example of how that works. Suppose you have a polynomial f(x) of degree n. I'll show a probabilistic algorithm that'll find an integer k such that f(k) != 0 with probability p >= 1/2.

Here goes: pick a random non-negative integer k below 2n. That's it, that's our answer.

What's the probability that f(k) != 0? Well, a polynomial of degree n can have at most n zeros, so at most n out of 2n non-negative integers below 2n are bad answers, so the probability of k being bad (i.e. f(k) = 0) is <= 1/2. Thus, probability of getting a correct answer is >= 1/2.

Now, probability 1/2 might seem pretty bad, we're, after all, rather likely to get a wrong answer. There's a simple way to deal with it, though: just repeat the algorithm as many times as you need. For example, if we repeat the algorithm 10 times, the probability of getting 10 wrong answers is 1/2^10 = 1/1024, rather small indeed. After 100 times, the probability of getting wrong answer is negligible.

Of course, it's easy to come up with an exact, non-probabilistic algorithm for the problem above. However, my probabilistic algorithm is O(1), while it's easy enough to prove that no constant time, non-probabilistic algorithm for the problem exists. I imagine that the situation is similar with the algorithm in the paper above: I'd wager that we get almost-linear time thanks to probabilistic nature.

Oh, and I was also cheating above somewhat: sure, my algorithm is O(1), but verifying that the answer is actually correct is O(n), so I cannot get an arbitrary small probability with my algorithm using the method above in constant time. The situation is, however, better in the context of maximum flow problem, because one can, in fact, check whether a flow is maximum in linear time, so that we can amplify the probability of getting a correct answer without losing the linear complexity.

Excusing such only encourages it IMHO. I think it was Einstein who said "If you can't explain it to a six year old, you don't really understand it." Stupid "mathies".