Why does the Torah see fit to mention the date that Yisrael arrived in Midbar Sin?
Rashi (citing the Gemara in Shabbos, 67b), Ramban (citing the Mechilta) and Rashbam: To teach us the miracle that the 'cakes' that they took with them out of Egypt lasted until now (sixty-one 1 meals).
See Sifsei Chachamim.
Why does it add "Bein Eilim u'Vein Sinai"?
In fact, before entering Midbar Sin, they first encamped at the Yam-Suf, and after they arrived in Midbar Sin, they went first to Dafkah and then to Alush, where the episode with the Manna took place, only the Torah did not bother to mention those details here (See Ramban). And it is in order to distinguish the location there from here that the Torah stresses in Chukas "Vayachnu Sham be'Midbar Tzin Hi Kadeish" (Ramban).
The Torah says that we arrived in Midbar Sin on the 15th of Iyar. It says in Shabbos (87b) that this was Shabbos. This is difficult for the opinion that we were commanded about Techumim in Marah!
Refer to 15:25:151:2 and the note there.
Riva, citing Tosfos Tuch: Really, we arrived before Shabbos, and complained the night after Shabbos (even though the verses connotes that both occurred on the 15th, i.e. Shabbos).
Based on Shabbos 87b: The one who holds that we were commanded about Techumim 1 holds that we did not travel from Refidim on Shabbos (and likewise, the 15th was not Shabbos, rather, on Sunday, like Seder Olam says - PF). 2
Mizrachi: We left Eilim on Friday, and arrived in Midbar Sin on Shabbos. 3
Divrei David: The Torah forbids only outside the Techum of 12 Mil (and Midbar Sin was within 12 Mil of Eilim. The Techum of one Mil is mid'Rabanan. 4 )
Nachalas Yakov: Even if Moshe already told them about Shabbos, they were not commanded to observe it until after the Manna fell.
Tosfos (87b DH a'Techumim): 'Techumim' includes the Isur of carrying in Reshus ha'Rabim. Ritva (87b DH Ka'asher) - the animals carried their Kelim. This opinion holds that likewise, they were not commanded about making animals work on Shabbos.
Iyar had only 29 days, and the Torah was given on the sixth of Sivan, on Shabbos. (PF)
I.e. we arrived shortly after Shabbos came. In that short time, no one left the Techum he received at the start of Shabbos. There was no Torah Isur of carrying or Mechamer (making animals work), because the Akirah (uprooting from rest) was before Shabbos.
Even though elsewhere (Taz YD 117:1), he himself wrote that Chachamim would not decree about something that the Torah explicitly permits, here it is not explicit (PF).
QUESTIONS ON RASHI
Rashi writes that the Manna began to fall on Iyar 16. Below (verse 35), he writes that it began to fall on the 15th!
Riva: Some say that it fell Bein ha'Shemashos between the 15th and 16th. 1
Riva: Below, Rashi means that it fell when 15 days remained in the month. This is like he says there that it ceased on the 15th of Nisan, Macharas ha'Pesach, i.e. the 16th, when 15 days remained in the month. .
Riva: This is wrong. Below (verse 8), Rashi writes that they received bread (manna) in the morning! The verses prove so. Also, they ate the last remnant from Mitzrayim on the night of the 16th. If the Manna already fell, why did they complain?! Also, the 15th was Shabbos! In Shabbos 87b, it says so, and that the manna fell the next morning. (Rashi ha'Shalem - all old texts of Rashi here say the 16th. In some recent texts, it says 15th; this is a mistake.)