This paper talks about several primary sources (i.e. Roman texts) that describe rolling Rs:
Terentianus Maurus writes in De litteris that
vibrat tremulis ictibus aridum sonorem
the R vibrates with a dry sound from trembling blows
Martianus Capella writes
R spiritum lingua crispante corraditur
[R] is pronounced with difficulty (?), with the tongue vibrating the air
Capella's writing contradicts itself on this count in another place, leaving this testimony in doubt.
Lucilius writes, more colorfully,1
r: irritata canis quam homo quam planius dictat
which (i.e. the sound r) an irritated bitch pronounces more clearly than a man
This is supposed to imply a growling similar to the modern instruction or R-rolling.
Taken as a group, these sources would seem to indicate that the Romans did roll some of their Rs. However, other authors, including Varro, Charisius, Marius Victorinus, and Martianus Capella (referring to his contradictory account), describe more fluid pronunciations. What this implies above all else is that pronunciations may have differed among different groups and in different time periods, hence the different accounts.
Indirect evidence for R-rolling comes from the Romance languages, where this is quite common. In Spanish, for example, rr indicates this rolling (rather than simply r). The presence of rolling in these languages suggests a common origin, likely in Latin.
1 The above translations are given by the author of the paper, and are not necessarily word-for-word. For example, brianpck suggested translating Lucilius differently, as "An irritated bitch which a man pronounces as clearly as possible."