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: *

*
**
*- There is no cube that can be divided into two cubes.
- There is only one square number which, augmented by $2$,

makes a cube, namely $25$.
- There are only two square numbers which, augmented by $4$,
make a cube, namely $4$ and $121$.
*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.