Bijecting a countably infinite set $S$ and its cartesian product $S \times S$

It's a little simpler to find a bijection $\mathbb{N}\to\mathbb{N}\times\mathbb{N}$ (e.g., think of the usual proof that $\mathbb{Q}$ is countable). There is also an easy bijection $\mathbb{Z}\to\mathbb{N}$, so you can use that to get a bijection $\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$.

A couple of comments, though: Herstein is only asking you to show that such a bijection exists, not to explicitly construct one. You could do so using any number of tools, including some that are in principle constructive but which you may not want to actually carry out. For example, there are obvious and easy embeddings $\mathbb{Z}\hookrightarrow \mathbb{Z}\times\mathbb{Z}$. If you also have an embedding $\mathbb{Z}\times\mathbb{Z}\hookrightarrow \mathbb{Z}$ you get the existence of a bijection between the two by using Cantor-Bernstein. For instance, you could take: $$(a,b)\longmapsto \left\{\begin{array}{ll} 2^a\times 3^b &\text{if $a,b\geq 0$;}\\ 3^b\times 5^{|a|} &\text{if $a\lt 0$, $b\geq 0$;}\\ 2^a\times 7^{|b|} &\text{if $a\geq 0$, $b\lt 0$;}\\ 5^{|a|}\times 7^{|b|} &\text{if $a,b\lt 0$.} \end{array}\right.$$ So with this you know there is a bijection $S\to S\times S$, even if you don't go through the rather annoying work of trying to write it out explicitly.

Also, it might be worth noting that if you drop the clause "and can be brought into one-to-one correspondence with the set of integers", then the resulting statement is equivalent to the Axiom of Choice (this is a result of Tarski's).

You can do it the following way:

1. Define $f\colon\mathbb{Z}\to\mathbb{N}$ to be any bijection (for example, $f(x) = 2x$ if $x\ge 0$ and $f(x) = -2x+1$ otherwise)
2. Define $g\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ your favourite bijection (e.g. $f(a,b) = \frac{(a+b+1)(a+b)}{2}+a$)
3. Assume $\sigma$ is a bijection of $S$ with $\mathbb{Z}$ then define: $\tau(s_1,s_2) = \sigma^{-1}(f^{-1}(g(f(\sigma(s_1)),f(\sigma(s_2)))))$

The proof that $\tau$ is a bijection is pretty straightforward, I think.

Of course you can skip many a step in this crazy composition by using Cantor-Schroeder-Bernstein theorem.

Edit:
I think I should expand a bit on the second part, as Arturo said in the comments to the original question. Assume $f\colon\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ a bijection, and $\sigma\colon S\to\mathbb{Z}$ then you have $\tau(s_1,s_2) = f(\sigma(s_1),\sigma(s_2))$ a bijection from $S\times S$ to $\mathbb{Z}$ and therefore you have both $S$ and $S\times S$ equinumerous with the integers, and therefore with each other.

In addition to Arturo's answer, recall that if you have a bijection between A and B, and one between B and C, you have a bijection between A and C by composition.