The performance concerns are probably negligible here. (They usually are.) If you're using
Java 1.5, consider returning an Iterable rather than an Iterator or any Collection. An Iterator can't be used in an enhanced for loop, while an Iterable can. But like an Iterator, and Iterable doesn't obligate you to get the whole thing in memory at once before you return any values. I.e. it offers the same advantage Ilja discussed for Iterator, except it works in an enhanced for loop. If you're not using JDK 1.5, and don't plan to in the future - what's wrong with you?!!
No, seriously, the answer to this question really depends on how you intend to use the method. I would suggest that it's usally better to declare your method to return a general interface (e.g. Collection, List, Iterator, Iterable) rather than a specific implementation (e.g. Vector or ArrayList) because it's always possible that later you'll discover it's advantageous to change implementations, and by using a generic interface whereever possible you make this easy to change.