Bnei Yisrael were given hok umishpat at Marah. Rashi explains that they were given a few mitzvot, including Shabbat. Afterwards, when they got to Eilim, they were given the mann. Why then, does the piyut of Dayenu in the Haggadah shel Pesah say "Ilu he'echilanu et hamann" before "Ilu natan lanu et HaShabat?"
The passage of the Manna goes into detail about proper Shabbos observance, and this is part of the study (according to Ramban) and perhaps also the practice (simple reading of Rashi) of the pre-Sinai Shabbos. This passage is in fact cited in the Gemara in connection with the laws of Shabbos. It was after the Manna first fell, so the order makes sense.