I think the best evidence is outlined by cmw's answer about transcriptions into Greek.
However, even just looking at Latin itself, the distribution of Latin consonantal V makes it fairly obvious that it was "originally" [w]. It's harder to find out from the language-internal evidence when the sound passed from [w] to [v]: much of the evidence I discuss below is consistent with this happening either late or early, since patterns in the distribution of sounds may lag sound changes (for comparison, present-day Russian [v], which is likewise from [w], still shows some behavior that is made easier to explain by the earlier value; likewise, Sanskrit va continues to pattern as a semivowel corresponding to u even though it had developed a labiodental pronunciation already in Panini's time).
The use of [w] in distantly etymologically related English words supports the reconstruction of [w] in the common ancestor that English and Latin share, Proto-Indo-European.
Evidence in Latin etymology that V derives from original [w]
Aside from V and U sharing the same spelling, there are a number of fairly regular alternations involving these two sounds in etymologically related words inside Latin. For example:
- "av" before vowels vs. "au" before consonants, as in avis vs. auspex (noted in a comment below by Draconis)
- "u" before a single vowel vs. "uv" before i + another vowel, as in fluo vs. fluvius
- "av" in a word-initial syllable vs "u" in a word-internal syllable, as in lavo vs. abluo
- "-uus" and "-vus" are variant forms of the same suffix
The V sound found in the above words was likely originally [w], because [w] and [u] are more similar and more likely to change into one another than [v] and [u].
The sound [u] is phonetically categorized as a "close back rounded vowel": "rounded" refers to the shape of the lips, which are brought together (there is a bit of variation between languages in the exact position of the lips). The sound [w] is pronounced mostly the same as [u], differing mainly in being non-syllabic. The sound [v] is further distinguished from [u] in several respects: 1) it is "labiodental", being pronounced with the lower lip against the upper teeth; 2) it has greater constriction than both [u] and [w], being categorized as a "fricative" consonant; 3) it lacks a "back" component.
Of course, once these patterns of alternation had been established, they could be maintained or extended to new pairs of words even after the sound change of [w] to [v].
For information on dating the change of [w] to [v], see the following question: When did the consonant U (i.e., V) begin to be pronounced as the fricative [v] instead of [w]?