I heard once that a Non-Jew had to pay back twice or three times the price of the object he stole to do teshuva. I can't find sources that confirm/infirm this.
How can a Non-Jew do teshuva for having stolen another Non-Jew?
Mi Yodeya is a question and answer site for those who base their lives on Jewish law and tradition and anyone interested in learning more. It only takes a minute to sign up.Sign up to join this community
In Ninvei they did Teshuva and it helped. Chazal say that they undid buildings in order to return a stolen beam. Seemingly, that was enough, or even extreme.
I do recall a Pirkei d'Rebbe Eliezer though, that says that 40 years later Ninvei returned to their bad ways and was destroyed. This was because they can't really do Teshuvah.