A Borel set whose projection onto the first coordinate is not a Borel set

You are not alone in finding this tough, as Lebesgue himself believed (in 1905) he had proved that the projection of a Borel set in $\mathbb{R}^2$ onto one of the axes was a Borel set. His error was discovered by Souslin which lead (I believe) to the process of Souslin schemes/hierarchy that he developed to investigate this problem.

R. M. Dudley "Real Analysis and Probability"

In my oldish edition it is covered in chapter 13, although my edition is by Chapman and Hall, whereas the Amazon edition is published by Cambridge. I am not sure that he actually gives a proof of the existence of such a set, but it is a good place to start, and he gives lots of references at the end of each chapter.

There is also another (older) book by Rogers on "Analytic Sets", but I don't have a copy so I can't check it.

The other answers are absolutely correct; let me add to them by giving an explicit example of such a set.

There is (think Godel numbering) a way to represent linear orderings with domain $\mathbb{N}$ by real numbers. Similarly, we can represent infinite sequences of natural numbers by real numbers. So we can define the following set:

$X$ is the set of pairs $(r, s)$ of real numbers such that $r$ codes a linear ordering and $s$ codes an infinite descending sequence through (the linear order coded by) $r$.

Let $Y$ be the projection of $X$ onto the first coordinate; then $Y$ is the set of reals which code non-well-orderings (or which fail to code linear orderings). This set, it turns out, is non-Borel! Meanwhile - as long as the coding scheme we used above is non-silly - $X$ is Borel.

Most of this is fairly straightforward; the hard part, of course, is proving that $Y$ is indeed not Borel. This is a bit technical, so I'm not going to get into it here; the citations in the other answers say more.

The projection of a Borel set in the square onto the $x$-axis is a so-called analytic set or Souslin set in the line. So you are asking for an analytic set in the interval that is not a Borel set. That is, an analytic set whose complement is not analytic. Any text on descriptive set theory should have such a construction. For example:

Donald L. Cohn, Measure Theory (Birkhäuser, 1980) Corollary 8.2.17, page 269

There is an analytic subset of $\mathcal N$ that is not a Borel set.

Here, $\mathcal N$ is homeomorphic to the irrationals in $(0,1)$, for example.

As a consequence, any uncountable complete metric space has such a set as well.