Gemara

(Rav Huna): If one is lost in the wilderness and does not know which day is Shabbos, he counts six days and guards the seventh [like Shabbos, and every seventh day after this];

(Rava): Every day other than 'his Shabbos' [is really Safek Shabbos, so] he does only Melachah necessary to live that day.

Objection: If he may not do even Melachah necessary to live on his Shabbos, he will die!

Correction: Rather, every day including his Shabbos he does only Melachah necessary to live that day.

Question: If so, how is his Shabbos different than the other days?

Answer: He makes Kidush at the start of the day, and Havdalah when it ends.

Rishonim

Rambam (Hilchos Shabbos 2:22): If one is in the wilderness and does not know which day is Shabbos, he is Mekadesh the seventh day from when he forgot. He blesses the Berachah of the day, and says Havdalah [at the end].

Rosh (7:1): Every day except for his Shabbos, he may walk [outside the Techum] in order to leave the Midbar. The Gemara asked 'how is his Shabbos different?' because it is not recognizable that he does not walk. Alternatively, also that day he may walk in order to leave the Midbar.

Ran (31a DH Moneh): He counts from the day that he realized that he forgot [which day of the week it is]. Each day he does the minimal amount of Melachah to live, for Piku'ach Nefesh. Therefore, we asked that if he does not do Melachah on Shabbos, he will die.

Ran (DH bi'Kedushah): Kidush and Havdalah are a mere commemoration, that he will have a day different than the others, and not forget Shabbos. Why don't we say that it is different, for that day he may not walk outside his Techum? Do not say that since it is not Piku'ach Nefesh, he may not walk any day. If so, he will always remain in the Midbar, be Mechalel Shabbos and die there! Rather, even on his Shabbos he may leave the Techum, since the Isur to leave the Techum is only mid'Rabanan.

Poskim

Shulchan Aruch (OC 344:1): If one is going in the wilderness and does not know which day is Shabbos, he counts seven days from the day that he realized that he forgot, and he is Mekadesh the seventh day through Kidush and Havdalah.

Mishnah Berurah (1): The same applies to one who was captured by Nochrim and forgot which day is Shabbos. However, sometimes he can use their calculation [of days] to determine our Shabbos.

Note: If one remembers which day of the week was the last Rosh Chodesh, the next Rosh Chodesh is on the next day of the week. The Molad (new moon) is at most two days before Rosh Chodesh. Or, perhaps he can calculate based on when the moon is full.

Mishnah Berurah (3): He makes proper Kidush and Havdalah on bread and wine. If he does not have them, he says Kidush and Havdalah in Tefilah. He prays the Tefilos of Shabbos on this day. He is Yotzei [Kidush] through this mid'Oraisa, even if today is really Shabbos. In pressed circumstances, one is Yotzei Havdalah through "Atah Chonantanu" in Shemoneh Esre.

Kaf ha'Chayim (5): Machazik Berachah brings from La'Menatze'ach l'David that the Shulchan Aruch connotes that he prays 18 Berachos even on his Shabbos. Even we would say all 18 Berachos on Shabbos, just Chachamim did not exert us to do so. He does not mention Shabbos, lest it is not Shabbos, and his Tefilah be false. The Heker of Kidush suffices. Nehar Shalom says that he prays Tefilas Shabbos. Mishbetzos Zahav derives so from the Rambam. Pesach ha'Dvir says that he prays Musaf according to Nehar Shalom, but not according to Machazik Berachah. I say that he prays Tefilas Shabbos because travelers do not always have wine or bread to say Kidush on them, so he must pray a Shabbos Tefilah to distinguish Shabbos and to be Yotzei Kidush. Do not say that only one without bread or wine prays a Shabbos Tefilah. People would mock this! There must be a uniform enactment. However, he does not pray Musaf, for Safek Berachos Lehakel.

Bi'ur Halachah (DH ha'Holech): Similarly, if he forgot which month it is, or which day of Nisan, Sivan or Tishrei, e.g. on days when the moon is not visible, he must observe the stringencies of the festivals, until the Yomim Tovim pass. Tosefes Shabbos says that if he can fast one day without danger, he may not do Melachah that day, for it is not Piku'ach Nefesh. Bigdei Yesha says that he need not afflict himself with fasting. This is a leniency so he can leave the Midbar promptly.

Note: Presumably, if it is Safek Yom Kipur, he should not eat or drink a Shi'ur to be liable (a large date, or Malei Lugmav of liquid, in the time to eat half a loaf), unless doing so would increase the amount of Melachah mid'Oraisa he must do.

Kaf ha'Chayim (2): If one is above the arctic circle, and the day [in mid-summer] lasts a month or two or more, he counts six days of 24 of our hours [from when he came there, and then observes Shabbos for 24 hours].

Teshuvos v'Hanhagos (5:84): In such a place, each new day begins when the sun is as low [in the sky] as it gets. There is no night. One may not go to live there, for he uproots from himself night Mitzvos. If one goes into space and circles the earth [e.g.] 16 times a day, he loses the concept of time in this world. He uproots himself from all Mitzvos dependent on time, e.g. Shabbos, Keri'as Shema and Tefilah. One may not do so. He is exempt for Melachah on Shabbos, but he is like one who is lost in the Midbar. He counts six days and is Mekadesh the seventh. The Ohr ha'Chayim (Shemos 31:15) learns from "Sheshes Yamim Te'aseh Melachah uva'Yom ha'Shevi'i Shabbos Shabboson" that one who does not rest on Shabbos must rest one day a week. Presumably he should observe Shabbos at the time of Shabbos in Yerushalayim - "Ki mi'Tziyon Tetzei Sorah...", even though there is a side to say that he observes like the place on earth from where he left.

Note: When a Yisrael astronaut went on the space shuttle, many Rabanan said that he keeps Shabbos according to the place he left earth.

Shulchan Aruch (ibid.): If he has [food], he may not do Melachah at all until he finishes what he has. Then he does Melachah each day, even on the day he is Mekadesh, enough for his minimal subsistence.

Beis Yosef (DH v'Chasav): The Ran connotes that he may do Melachah only if he is an Oni without any way to feed himself other than what he earns with the others in the caravan. If he has, he may not do Melachah at all until he finishes what he has. Then, each day he works what is needed for that day. The Kolbo explicitly says so.

Taz (1): His only Heter is for Piku'ach Nefesh. Therefore, if he has bread, he may not cook food. He may transgress Techumim because it is only mid'Rabanan, and every day is a Safek.

Magen Avraham (1): Even though most days are weekdays, this is considered a Safek Kavu'a (fixed. It is considered an even Safek.)

Mishnah Berurah (4): If he has bread, he may not work for the caravan to buy a cooked food, for this is not Piku'ach Nefesh.

Kaf ha'Chayim (11): Pesach ha'Dvir says that even if he is in the Midbar a long time, he can live on bread alone, unlike Nezirus Shimshon.

Mishnah Berurah (5): If he has money or something to sell, or can get a loan or gift from the caravan, he may not work.

Bi'ur Halachah (DH Afilu): I say that he must wear Tefilin every day. Most days are weekdays. We must follow the majority. Kidush is a mere commemoration. The Isur Melachah is because Chachamim considered it a Safek Kavu'a. Even if we will say that his Shabbos is Kavu'a mid'Oraisa and it is considered an even Safek, it is a Safek mid'Oraisa [that he must wear Tefilin today]. Even though the Magen Avraham forbids even Shevus [Isurim mid'Rabanan] on his Shabbos, like Yom Tov Sheni, this is a mere stringency. Even though Yom Tov Sheni is exempt from Tefilin, that was an enactment for all of Yisrael, lest they come to desecrate Yom Tov. They made it totally like Yom Tov [except for burying Mesim], lest people disgrace it. Chachamim can tell people to passively transgress Torah law. Yom Tov Sheni is even for us, who [have a fixed calendar and] know when each month begins! Chachamim did not enact to uproot weekday Mitzvos from one who forgot. Also, Shabbos is exempt from Tefilin because the day is an Os [a sign]. This man works every day to live. Nothing is a sign [that today is Shabbos]! Kidush is not enough. The primary Os is ceasing from Melachah to show that Hash-m ceased. A dangerously sick person who may transgress Shabbos has this Os, for he ceases from Melachah not needed for his Refu'ah. The one who forgot does the same minimal Melachah every day. Also, all Yisre'elim around a sick man cease on Shabbos [so this is an Os]. The reason of Os is not so clear, but the first reason suffices to obligate him. However, he should not wear Tefilin while praying Tefilos Shabbos, lest he contradict himself. Also, if he would not wear Tefilin on his Shabbos, this would answer how Shabbos is different, according to Tosfos, that refraining from something is a Heker.

Note: Even according to the Mishnah Berurah, there is a Heker that on his Shabbos he prays without Tefilin. Perhaps the Gemara wanted to find a Heker even for one who does not have Tefilin!

Kaf ha'Chayim (6): Shabbos Shel Mi says that he wears Tefilin every day. Pesach ha'Dvir says that he does not wear on his Shabbos, and never blesses, due to Safek.

Shulchan Aruch (ibid.): He may walk every day, even on the day he is Mekadesh.

Beis Yosef (DH u'Mah she'Chasav): The first answer of the Rosh holds that he may not leave his Techum on his seventh day. The Tur held that the latter answer is primary. Also Tosfos, the Ran, and the Magid Mishneh citing the Ramban say so.

Magen Avraham (3): Even according to the opinion that Techumim are mid'Oraisa, since there is no Isur Skilah for them, Chachamim were not stringent. Tosfos and the Rosh say that we are lenient to enable him to speed up leaving the Midbar. This implies that he may not do other Isurim mid'Rabanan. Even though we are lenient about a Safek mid'Rabanan, since Shabbos takes effect on him, he is forbidden every day, just like Yom Tov Sheni, which is also a Safek mid'Rabanan.

Mishnah Berurah (9): Eliyahu Rabah is lenient about mid'Rabanan laws, even on his seventh day, since it is a Safek mid'Rabanan.

Kaf ha'Chayim (21): Tosefes Shabbos is stringent about Shevus on all days.

Kaf ha'Chayim (22): He may not make his animal work unless it is Piku'ach Nefesh.

Note: The Magen Avraham said that we are lenient about Techumim even if it is mid'Oraisa, since there is no Skilah for it!

Bi'ur Halachah (DH Metzumtzemes): Why didn't Chachamim allow him to do much Melachah on one or two days, more than he needs, to enable him to desist from Melachah four or five days? It is likely that he would fulfill Shabbos properly mid'Oraisa! When he does the minimum each day, this is not Chilul Shabbos, for it is Piku'ach Nefesh. This is better than doing extra Melachah on one or two days, which is a Safek willful Chilul Shabbos.

Note: If today one may get extra food through a Melachah mid'Rabanan or unskillfully, or increasing the Shi'ur (e.g. cut off a branch with many fruits, even though a branch with fewer would suffice for today), to spare himself from doing a Melachah mid'Oraisa tomorrow, perhaps all would permit.

Bi'ur Halachah (ibid.): We can learn from here to a soldier who must do a Melachah mid'Oraisa. If he can do it on Erev Shabbos, surely he must do so, to avoid Chilul Shabbos tomorrow. Even if he could not do it until Bein ha'Shemashos, it is better to do Melachah tomorrow, even though it is surely Shabbos, for then he is forced, and it is not forbidden. If he does it now, he willingly transgresses b'Safek. We can reject this. Here, we discuss two days. The soldier must do Melachah on one day. The beginning of the 24 hours of Shabbos is no different than the middle. It is better that he do it immediately, for perhaps he will save himself from Chilul Shabbos.