Infinite Chomp is a finite game?

It says that a "finite" game is one that is guaranteed to end. This is the case for Chomp.

Let's consider a couple of simpler examples that illustrate the same point. In Game A, player 1 begins by naming any positive integer. Player 2 then names a strictly smaller positive integer. The players than alternate naming smaller and smaller integers; the player who names 1 leaves her opponent with no legal move, and so wins.

Clearly Game A is finite; it cannot continue forever. In fact, after the first move by Player 1, you can place an upper bound on the number of moves it will take to finish. But before that first move, you cannot bound how long it will take to finish the game.

In Game B, the board is a quarter-infinite chessboard that extends forever to the north and east. Player 1 begins by placing a token on any square of the board. A legal move is then to move the token any number of squares toward the west edge, or to move the token to any square of a row that is farther south. Observe that once the token is on the first (southernmost) row, the game is essentially Game A. So once the token is in the first row, the game can be bounded: if the token is in the $n$th square of the first row, the game lasts at most $n$ more moves.

But suppose the token is in the $n$th square of the second row. The game cannot be bounded, but it cannot last forever either. Because after at most n moves, the token must be in the first row, and at that point it can be bounded.

Now suppose the token is in the $n$th square of the third row. The game cannot be bounded, but it cannot last forever either. Because after at most n moves, the token must be in the second (or first) row and although it may not be boundable then, we can at least place a bound on how long before it is bounded.

After player 1's first move, the token is on some row, and although we can't place a bound on how long the game will last, we can be sure it can't go on forever, because after some bounded number of moves, the token must move southwards. Before player 1's first move we can't even do that, but we can still be sure the game won't go on forever, because we can guarantee that after a bounded number of moves (1 move, in fact) we will be able to bound the number of moves before we can bound the number of moves before… (etc.) we can bound the game. The game is unboundedly unbounded, but it must end eventually.

Chomp on an infinite chocolate bar is of this type. The first bite leaves behind a finite number of infinite rows and columns, and although we can't bound the game at that point, we can bound the number of moves before the number of infinite rows and columns must be reduced. So even though the game is undoundedly unbounded, it must still end sometime.

I think the distinction you may be missing here is the difference between $\omega$ as a set — that is, the set of all natural numbers $\{0,1,2,\ldots\}$— and $\omega$ as an ordinal, the entity which corresponds to the ordering $0\lt1\lt2\lt3\lt\ldots$ of the naturals. The two concepts are obviously closely related, but they're not quite identical; for instance, consider $\omega+\omega$, defined as the set $\{0,1,\ldots,\omega, \omega+1, \ldots\}$ and similarly as the ordering $0\lt1\lt\ldots\lt\omega\lt\omega+1\lt\ldots$ on those entities. Then there's a simple isomorphism from the set $\omega+\omega$ to the set $\omega$: for all integers $i$, map $i$ to $2i$ and map $\omega+i$ to $2i+1$. But the two aren't isomorphic as ordered sets; every element in $\omega$ has an immediate predecessor, but the element $\omega$ in the order $\omega+\omega$ doesn't have one. To see why ordinals are the right concept, consider the nearly-trivial $1\times\omega$ version of Chomp; then the positions of this game correspond precisely to the ordinals $0, 1, \ldots, \omega$, and we can move from a position $P$ to a position $Q$ precisely if $Q\lt P$; we have a natural order on positions.

Now, let's take a look at the $2\times\omega$ case: positions of $2\times\omega$ Chomp aren't ordinals themselves (they're pairs $(m,n)$ with $0\leq m\leq n\leq\omega$), but the key point is that we can put them into one-to-one correspondence with ordinals, in such a way that every legal chomp move takes us to a lower ordinal; that is, there's an order-preserving isomormphism between the two. To see this, we can break things into two cases: $n$ finite and $n=\omega$. For $n$ finite, there are obviously $n+1$ different values $(0,1,\ldots,n)$ for $m$; each of these is reachable from the positions with the same $n$ and higher $m$, but none is reachable from any position with lower $n$, so we can order them $(0,0)\lt(0,1)\lt(1,1)\lt(0,2)\lt(1,2)\lt\ldots$ — that is, by increasing $n$, with $m$ increasing within each value of $n$; you should be able to construct an order isomorphism that maps this portion of the overall order of positions into the order $\omega$. Now, 'after' these we can put all the positions with $n=\omega$ and $m$ finite, ordered by $m$: $(0,\omega)\lt(1,\omega)\lt(2,\omega)\ldots$; this is trivially order-isomorphic to $\omega$. And finally, after all these comes the initial position $(\omega,\omega)$. This gives us an overall order of order-type $\omega+\omega+1$ on the set of all $2\times\omega$ Chomp positions; we know that from any given position $P$, any legal move to a position $Q_i$ will have $Q_i\lt P$ under this ordering.

So how does this help? Well, it helps because the ordinals are (essentially by definition) well-ordered — any set of ordinals has a least element, and so in particular there can be no infinite descending chain $O_0\gt O_1\gt O_2\gt\ldots$ (this is closely related to the Axiom of Foundation/Axiom of Regularity in set theory). As others have said, this is what's meant by the game being finite; there's no specific bound on how long the game could take, but there's no infinite sequence of plays available from the starting position.

The $\omega\times\omega$ case is substantially more complicated, but it still falls to a similar analysis; the key is that each position can be mapped to some ordinal in order-preserving fashion. One way of doing this: suppose the initial bite is at $(m,n)$ with $n\gt m$ (an obvious symmetry applies). Then we can think of the bite as splitting the bar up into two $n\times\omega$ Chomp bars, the 'horizontal' and 'vertical' leftovers $B_h$ and $B_v$ (with one of these sub-bars already having been chomped down to an $m\times\omega$ piece). But since each of $B_h$ and $B_v$ is a subposition of a $n\times\omega$ position, there are individual horizontal and vertical well-orderings $H = (H_0\lt H_1\lt\ldots)$ and $V = (V_0\lt V_1\lt\ldots)$ on them (you can see how to order the $n\times\omega$ positions for any $n$ in a fashion analagous to the $2\times\omega$ positions); and we can combine the horizontal and vertical orderings to form the product order, $H\cdot V = ((H_0, V_0)\lt (H_1,V_0)\lt\ldots\lt(H_0,V_1)\lt(H_1,V_1)\lt\ldots)$ (see http://en.wikipedia.org/wiki/Ordinal_arithmetic for more details on this process). Finally, we can stack all of these positions up by increasing $n$ (the 'size' of the original bite - or more abstractly, the smallest value of $n$ such that there are no uneaten points northeast of $(n,n)$). It's hard to piece all of these together, but hopefully you can get some sense of how this offers an overall well-ordering on the set of possible $\omega\times\omega$ Chomp positions. Once we have that well-ordering, what its specific type is isn't relevant - merely the fact that it is a well-ordering is enough for the well-foundedness principle to apply and for us to conclude that the game is finite.

The game is not finite in the sense that there is a number $N$ and we can prove the game will end in $N$ moves. It is finite in the sense that the game can't go on forever. Consider the $2\times \infty$ example. The first move must take a bite from the top row. There are now a finite number of pieces left in the top row. Eventually a player will also take a bite from the bottom row (because there were only finitely many moves available in the top row after the first move, this has to happen). Once a player takes a bite from the bottom row, there are a finite number of remaining pieces.