<p>I have a set of objects in a Vector from which I'd like to select a random subset (e.g. 100 items coming back; pick 5 randomly). In my first (very hasty) pass I did an extremely simple and perhaps overly clever solution:</p>

<pre><code>Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);
</code></pre>

<p>While this has the advantage of being nice and simple, I suspect it's not going to scale very well, i.e. Collections.shuffle() must be O(n) at least. My less clever alternative is</p>

<pre><code>Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i &lt; 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}
</code></pre>

<p>Any suggestions on better ways to draw out a random subset from a Collection?</p>

Your second solution of using Random to pick element seems sound, however:
Depending on how sensitive your data is, I suggest using some sort of hashing method to scramble the random number seed.  For a good case study, see
How We Learned to Cheat at Online Poker
(but this link is 404 as of 2015-12-18). Alternative URLs (found via a Google search on the article title in double quotes) include:
How We Learned to Cheat at Online Poker
— apparently the original publisher.
How We Learned to Cheat at Online Poker
How We Learned to Cheat at Online Poker
Vector is synchronized.  If possible, use ArrayList instead to improve performance.