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?
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.