In this specific paper we are talking about when k=3, that is "Is there a positive integer s such that every natural number can be expressed as the sum of s cubes?"
A result by Dickson in 1939 showed that every integer (except 23 and 239) can be represented by the sum of 8 non-negative cubes. This was further refined by Linnik who showed that large enough integers can always be represented by 7 cubes (more details in the paper, I'm just summarising).
This paper provides support for the conjecture that for sufficiently large integers you only need 4 cubes, and find a possible lower bound on what large enough means - greater than 7373170279850.
It's relatively easy to show that 7373170279850 cannot be written as the sum of four cubes. The hard aspect is finding such a number in the first place, and then determining if it is the largest such number.
Their method was to find a number N_1 that is not C_4 (where C_s means it can be written as the sum of s cubes), and then check every number between [N_1, 10.N_1]. They chose the number 10 by simulating pseudo-cubes sequences, which gave them confidence 10 is a good choice. If you find a number that is C_4 in the interval, call this N_2 and repeat the process, if you don't then you have found a candidate for the largest.
There are some more details about number theory tricks they used to reduce the search space in the paper, but that seems to be the gist of the whole thing.
[Edited to include more information from the paper]
[0] direct link to the paper: http://www.ams.org/journals/mcom/2000-69-229/S0025-5718-99-0...