The first step towards rhotacism is believed to have been voicing of single "s" to the sound [z] in between vowels (and also after a vowel and before the semivowel *v* [w]; thanks to TKR for pointing this out in a [comment][1]).  This kind of voicing change is common historically; for example, it also occured between Classical Latin and many Romance languages. Double *ss* remained unvoiced.

In some related languages, such as Oscan, /z/ remained as such between vowels and did not undergo rhotacism. We know this because we have Oscan inscriptions written in the Latin alphabet that use the letter Z for this sound (Buck 1904). 

The next step of rhotacism (z > r) is a little less common across languages, but we do have some other examples. The process also applied historically in Germanic; one place where you can see the result in English is *forlo**r**n,* which is historically related to the verb *lo**s**e*.

As a result of these changes, original intervocalic *\*s* ultimately became *r* in Classical Latin. In the ancestor of Latin, *\*s* seems to have also been voiced to [z] after the voiced consonant /r/, so another related sound change is original *\*rs* to Classical Latin *rr.* One word that shows this change is [*terra*][2] "earth," from Proto-Indo-European *\*ters*- ‎(“dry”). The cluster *rs* that occurs in Classical Latin is a simplification of earlier *\*rtt* or *\*rts*; this is why most words with *rs* also have *rt* in some forms or in related words (such as [*ars*][3] "art," genitive *artis*).

Aside from these three environments (between vowels, between a vowel and *v,* and after *r*) I can't think of any other cases where Latin *r* came from earlier *\*s.* Once the sound *r* became established in certain words, their derivatives might come to have it in other environments. For example, as Joonas Ilmavirta mentions, some words such as *honor* developed final *r* instead of *s* after a vowel; it's believed this is due to the presence of *r* in other related forms (like *honoris*). There also seem to be some words with *r* before another consonant where the *r* was originally intervocalic *\*s*, but the following vowel was lost (as in [*veternus*][4]).

There are also words in Classical Latin that had intervocalic single *s,* which we believe was pronounced [s]. Many of these correspond to etymological *\*ss* which seems to have become shortened in some words. In other cases, intervocalic *s* has been explained as originating in borrowings from other Italic languages that did not undergo rhotacism. Whatever the reason, their presence indicates that rhotacism was not active as an automatic sound change in the Classical era (Gorman).

Bibliography:

- Buck, Carl Darling. 1904. [*A grammar of Oscan and Umbrian : with a collection of inscriptions and a glossary*][5]
- Gorman, Kyle. "[Latin Rhotacism for Real][6]"


  [1]: http://latin.stackexchange.com/questions/136/rhotacism-why#comment237_146
  [2]: https://en.wiktionary.org/wiki/terra#Latin
  [3]: https://en.wiktionary.org/wiki/ars#Latin
  [4]: https://en.wiktionary.org/wiki/veternus
  [5]: https://archive.org/stream/grammarofoscanum00buckuoft#page/74/mode/2up
  [6]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.225.8217&rep=rep1&type=pdf