Escritura concurrente en Fichero

La pregunta que planteas es muy interesante.
La respuesta está en los hilos de Java, y el método synchronized.
Te adjunto una solución: creas una clase que se encargue de escribir en el fichero, con un método synchronized, y después creas hilos que accedan a ella.
Por ejemplo:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
public class ControladorDelFichero
{
    private File fichero;
    private PrintWriter pw;
   public ControladorDelFichero()
   {
     try {
         fichero = new File("Fichero");
         pw = new PrintWriter(fichero);
    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
   }
   public synchronized void println(String cadena)
   {
       pw.println(cadena);
   }
   public synchronized void cierra()
   {
       pw.close();
   }
}
Esa sería la clase que pinta en el fichero, para ello, si te fijas, el método println es de tipo "synchronized", que se encarga de sincronizar el método con hilos concurrentes, de tal manera que si dos hilos han pedido utilizar el método, sólo uno de ellos podrá ejecutarlo, y el segundo se mantendrá a la espera hasta que el primero haya terminado de ejecutar el método.
Un ejemplo de definición de hilo en Java es el siguiente:
public class Hilos1 extends Thread {
    public void run() {
        System.out.println("Hilos1");
    }
};
Si te fijas, basta con extender de Thread y sobreescribir el método run.
Para ejecutarlo, desde el main, tienes que hacer lo siguiente:
public class Main {
    /**
     * @param args
     */
    public static void main(String[] args) {
        Hilos1 hilos1 = new Hilos1();
        Hilos2 hilos2 = new Hilos2();
        hilos1.start();
        hilos2.start();
    }
}
Prueba y me cuentas,
Jaime.

Hola, en primer lugar, muchas gracias por tu respuesta. Está todo muy bien explicado. Sólo me quedan un par de dudas:
1) Según el ejemplo que me has puesto, tengo la clase "ControladorDelFichero", que es la que tiene el método sincronizado encargado de escribir correctamente en el fichero. Entonces, según esta clase, tendría que hacer algo así, ¿no?
public class HilosEscritura extends Thread {
    private String texto;
    private ControladorDelFichero controlador;
    public HilosEscritura (String t,ControladorDelFichero c)
    {
           texto=t;
           controlado=c;
    }
    public void run() {
        c.println(texto);
    }
};
public class Main {
    /**
     * @param args
     */
    public static void main(String[] args) {
       ControladorDelFichero c=new ControladorDelFichero();
        Hilos1 HilosEscritura = new HilosEscritura("hola",c);
        Hilos2 HilosEscritura = new HilosEscritura("adios",c);
        hilos1.start();
        hilos2.start();
    }
}
¿Esto está bien?
2) La otra cuestión, es que 2 clientes pueden estar trabajando al mismo tiempo con el mismo fichero, y modificándolo cada uno por su cuenta. Entonces, a la hora de grabarlo, si lo escriben a la vez el tema está resuelto con lo que me has explicado. Pero lo veo algo complicado, es decir, si el primero guarda algo, el segundo siempre se lo va a pisar, ¿no? No se si me explico. ¿Hay alguna manera de controlar esto 'elegantemente'?
Muchas gracias!