How do we know that Fermat wrote his famous note in 1637?

Not only do we not know the date, we don't even know whether he wrote the remark at all. For all we know it might have been invented by his son Samuel, who published his father's comments.

In his letters, Fermat never mentioned the general case at all, but quite often posed the problem of solving the cases $n=3$ and $n=4$. I am almost certain that Fermat discovered infinite descent around 1640, which means that in 1637 he did not have any chance of proving FLT for exponent 4 (let alone in general).

In 1637, Fermat also stated the polygonal number theorem and claimed to have a proof; this is just about as unlikely as in the case of FLT -- I guess Fermat wasn't really careful in these early days.

Let me also mention that Fermat posed FLT for $n=3$ always as a problem or as a question, and did not claim unambiguously to have a proof; my interpretation is that he did not have a proof for $n = 3$, and that he knew he did not have one.

Edit Let me briefly quote two letters from Fermat:

I. Oeuvres II, 202--205, letter to Roberval Aug. 1640 Fermat claims that if $p = 4n-1$ be prime, then $p$ does not divide a sum of two squares $x^2 + y^2$ with $\gcd(x,y) = 1$. Then he writes

I have to admit frankly that I have found nothing in number theory that has pleased me as much as the demonstration of this proposition, and I would be very pleased if you made the effort of finding it, if only for learning whether I estimate my invention more highly than it deserves.

This looks as if Fermat had just discovered "his method" of descent. Starting from $x^2 + y^2 = pr$ one has to show that there is a prime $q \equiv 3 \bmod 4$ dividing $r$ which is strictly less than $p$.

II. In his letter to Carcavi from Aug. 1659 (Oeuvres II, 431--436), Fermat writes:

I then considered certain questions which, although negative, do not remain to receive a very great difficulty, for it will be easily seen that the method of applying descent is completely different from the preceding [questions]. Such cases include the following:

1. There is no cube that can be divided into two cubes.
2. There is only one square number which, augmented by $2$,
   makes a cube, namely $25$.
3. There are only two square numbers which, augmented by $4$, make a cube, namely $4$ and $121$.
4. All squared powers of $2$ augmented by $1$ are prime numbers.

My interpretation of this is that Fermat lists four results which he believes can be proved using his method of descent. In my opinion this implies that Fermat did not have a proof of FLT for exponent $3$ in 1659.

Edit 2 In light of the discission at wiki.fr let me add a couple of additional remarks along with a promise that a nonelectronic publication of my views on Fermat will appear within the next two years (if I can find a publisher, that is).

A search in google books for "hanc marginis" and Fermat for the years up to 1900 reveals several hits, none of which claims that the remark was written around 1637; in particular there are no dates given in Fermat's Oeuvres or in Heath's Diophantus. Starting with Dickson's history, this changes dramatically, and nowadays the date 1637 seems to be firmly attached to this entry.

The dating of the entry seems to come from a letter written by Fermat to J. de Sainte-Croix via Mersenne mentioned in Nurdin's answer; this letter is not dated, but since Descartes, in a letter to Mersenne from 1638, refers to a result he credits to Sainte-Croix, but which Fermat claims he has discovered, it is believed that Fermat's letter to Mersenne was written well before that date. The reasons for dating it to September 1636 are not explained in Fermat's Oeuvres.

In this letter, Fermat poses the problem of finding two fourth powers whose sum is a fourth power, and of finding two cubes whose sum is a cube. The reasoning seems to be that in 1636, Fermat had not yet found (or believed to have found) a proof of the general theorem, so the entry must have been written at a later date. Since he did not refer to the general theorem in any of his existant letters, it is also believed that he soon found his mistake, so the entry cannot have been written at a time when Fermat was mature enough to find sufficiently difficult proofs.

Let me also add that the following dates can be deduced from Fermat's letters:

• 1638 Numbers 4n-1 are not sums of two rational squares
• 1640 Fermat's Little Theorem
• 1640 Discovery of infinite descent; used for showing that (1) primes 4n-1 do not divide sums of to squares.
• 1640 Statement of the Two-Squares Theorem
• 1641 - 1645 Proof of (2) FLT for exponent 4
• later: Proof of (3) the Two-Squares Theorem

It is impossible to attach any dates between 1644 and 1654 to Fermat's discoveries since he either wrote hardly any letter in this period, or all of them are lost.

Fermat claimed to have discovered infinite descent in connection with results such as (1), and that he at first could apply it only to negative statements such as (2), whereas it took him a long time until he could use his method for proving positive statements such as (3). Thus the proofs of (1) - (2) - (3) were found in this order.

This means in particular that if Fermat's entry in his Diophantus was written around 1637, then the marvellous proof must have been a proof that does not use infinite descent.

I would also like to remark that the Fermat equation for exponents 3 and 4 had already been studied by Arab mathematicians, such as Al-Khujandi and Al-Khazin, who both attempted proving that there are no solutions. The cubic equation also shows up in problems posed by Frenicle and van Schooten in response to Fermat's challenge to the English mathematicians.

There is a letter from Fermat to Mersenne, sent in September 1636, where Fermat proposes such problem:

$3^o$. Invenire duo quadratoquadratos quorum summa aequetur quadratoquadrato, aut duos cubos quorum summa sit cubus.

or "Find two fourth powers, whose sum is the fourth power or two cubes, whose sum is a cube."

So, Fermat definitely had thought about this problem in 1636. The letter could be found here.

There are also other letters, where he mentions these problems(for example letter to Mersenne from may of 1640), but they were written later.

Below is Andre Weil's opinion on this general topic, from his historical treatise Number Theory, p.104.

As we have observed in Chap. I, S.X, the most significant problems in Diophantus are concerned with curves of genus 0 or 1. With Fermat this turns into an almost exclusive concentration on such curves. Only on one ill-fated occasion did Fermat ever mention a curve of higher genus, and there can hardly remain any doubt that this was due to some misapprehension on his part, even though, by a curious twist of fate, his reputation in the eyes of the ignorant came to rest chiefly upon it. By this we refer of course to the incautious words "et generaliter nullam in infinitum potestatem" in his statement of "Fermat's last theorem" as it came to be vulgarly called: "No cube can be split into two cubes, nor any biquadrate into two biquadrates, nor generally any power beyond the second into two of the same kind" is what he wrote into the margin of an early section of his Diophantus (Fe.I.291, Obs.II), adding that he had discovered a truly remarkable proof for this "which this margin is too narrow to hold". How could he have guessed that he was writing for eternity? We know his proof for biquadrates (cf. above, S.X); he may well have constructed a proof for cubes, similar to the one which Euler discovered in 1753 (cf. infra, S.XVI); he frequently repeated those two statements (e.g. Fe.II.65,376,433), but never the more general one. For a brief moment perhaps, and perhaps in his younger days (cf. above, S.III), he must have deluded himself into thinking that he had the principle of a general proof; what he had in mind on that day can never be known.