Antes que nada, veamos un pequeño ejemplo del uso de la clase Random, para ver su funcionamiento básico:

import java.util.*;
public class NumerosAleatorios
{
public static void main(String args[])
{
Random r=new Random();
r.setSeed(123456789);
System.out.println(r.nextInt(1000));
}
}

Como puedes observar, después de crear el objeto Random, es necesario utilizar el método setSeed(long) para establecer la semilla a partir de la cual se generarán números aleatorios (pseudo-aleatorios)... fíjate como le pasamos un número(que puede ser cualquiera, en formato long logicamente [obviando o no el sufijo L]), que representará la semilla.

Lo primero que es necesario entender, es que con la clase Random se generan números pseudo-aleatorios, por tal motivo siempre que corras el programa te va a salir exactamente el mismo número aleatorio o la misma secuencia (a menos de que se cambie la semilla). Esto se puede observar en el propio método setSeed:

synchronized public void setSeed(long seed) {
this.seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1);
haveNextNextGaussian = false;
}

Entonces... ¿cuál es la solución para generar números realmente aleatorios con la clase Random? El método más sencillo para hacer esto, es insertar un valor en la semilla (en el método setSeed) que cambie cada vez que se ejecute el programa, y el más adecuado es la hora. Por obvios motivos, cada vez que ejecutas un programa la hora y fecha ha cambiado, entonces podemos usar nuestro programa de la siguiente forma:

import java.util.*;
public class aleatorio
{
public static void main(String args[])
{
Random r;
r=new Random();
r.setSeed(new Date().getTime());
System.out.println(r.nextInt(1000));
}
}

De ésta manera la semilla cambiará cada vez que ejecutemos el programa.