What is the proper teshuva for a non-Jew who had intimate relations with a married woman (non-Jew as well)?
Rambam in Hilchos Teshuva Chap 2 (2) specifies how to do teshuvah:
What constitutes Teshuvah? That a sinner should abandon his sins and remove them from his thoughts, resolving in his heart, never to commit them again as [Isaiah 55:7] states "May the wicked abandon his ways...." Similarly, he must regret the past as [Jeremiah 31:18] states: "After I returned, I regretted."
[He must reach the level where] He who knows the hidden will testify concerning him that he will never return to this sin again as [Hoshea 14:4] states: "We will no longer say to the work of our hands: `You are our gods.'"
He must verbally confess and state these matters which he resolved in his heart.
abandon the sin
regret the sin
confess the sin
resolve never to repeat that sin.
There is no specific method of teshuvah for specific sins. It certainly helps to study the halochos related to the sin.
As it happens, the Rambam uses the example of illicit relations to show the test of true teshuvah in 2
[Who has reached] complete Teshuvah? A person who confronts the same situation in which he sinned when he has the potential to commit [the sin again], and, nevertheless, abstains and does not commit it because of his Teshuvah alone and not because of fear or a lack of strength.
For example, a person engaged in illicit sexual relations with a woman. Afterwards, they met in privacy, in the same country, while his love for her and physical power still persisted, and nevertheless, he abstained and did not transgress. This is a complete Baal-Teshuvah. This was implied by King Solomon in his statement [Ecclesiastes 12:1] "Remember your Creator in the days of your youth, [before the bad days come and the years draw near when you will say: `I have no desire for them.'"]
Edit- added later.
The answer did not specifically address the part of the the question relating to non-Jews.
Regarding non-Jews this Chabad article says:
…... non-Jews can and must perform teshuvah.
We explained that there is a basic level of teshuvah, which is simply the decision to not sin again. Thereby, one may be considered a “righteous person” from the time this teshuvah is performed and thereafter. Then there is a higher level of teshuvah, consisting of regretting the sins, confession, and in certain cases, other factors as well.
It is the first category of teshuvah that applies to non-Jews, as well as to Jews. If they have sinned, they must make efforts to change their ways and desist from sinning in the future. Indeed, by doing so they may spare themselves from punishment, as was the case with the people of Nineveh. They are not, however, afforded the special opportunity to rectify the past through regret and confession, thereby wiping the slate clean. According to this approach, this more complete form of teshuvah is reserved for the Jewish people only. This distinction can be understood based on an explanation given by Rabbi Moshe Di Trani, in his work Beit Elokim: Since Jews have six hundred and thirteen mitzvot, it is expected that at times Jews will succumb to sin. Non-Jews, on the other hand, only need to observe seven mitzvot and as such are expected not to fail in their observance in the first place.
Despite that, the author writes in an answer to a question:
…... it is possible that Righteous gentiles actually fall in the same category as Jews with regard to Teshuva and can also reach the higher level of teshuva which wipes the slate clean.
So the non-Jew must try to change and stop sinning in the future. It seems that it may be possible for him to go further and follow the same prescriptions that the Rambam lays down for Jews.
In short, there's no Teshuvah for non-Jews. And please don't kill the messenger (me).
- OF COURSE he might regret and be sorry and it is surely a good thing but this does not constitute Teshuva in our terms. Avrohom in his answer brought a Chaba article that starts with the following words:
"The Jerusalem Talmud, Nazir, beginning of Chapter 9. as well as the Midrash Tanchuma Parshat Haazinu, 4 seem to indicate that while Teshuvah atones for a Jew’s sins, it does not atone for the sins of a non-Jew."
The Jewish system of Mitzvos is very different from the system of non-Jews, for example, Jews are not punished for all monetary misdeeds (theft, wage withholding etc) as they all can be repaid (paid back later), but a non-Jew who stole a thing is capitally punished and he can not return the theft to undo his sin (Rambam Melachim).
Same with Teshuva, sorry to disappoint you, it is reserved for the Jews only (it is also a positive Mitzvah). So a Jew can [theoretically] fix his misdeed by doing Teshuva (described in Rambam for example), but a non-Jew that sinned has no such option.
Both Jews and non-Jews can decide to stop sinning in the future, but this does not annulate what's already done per se.
Even for Jews, for such a serious sin, a simple regret is not enough, Yom Kippur AND suffering are requiered also, and non-Jews don't have Yom Kippor. As Rambam Teshuva 1, 4:
"עבר על כריתות ומיתות בית דין ועשה תשובה תשובה ויוה"כ תולין ויסורין הבאין עליו גומרין לו הכפרה ולעולם אין מתכפר לו כפרה גמורה עד שיבואו עליו יסורין"
"If a person violates sins punishable by karet or execution by the court and repents, Teshuvah and Yom Kippur have a tentative effect and the sufferings which come upon him complete the atonement. He will never achieve complete atonement until he endures suffering for concerning these sins..."
- On the positive side, he can always convert and start a new life with a new Jewish soul that automatically annulates all his non-Jewish sins. Well, not really annulates, it's just a brand new soul, so I have no idea what happens to the old non-Jewish soul.