Se usi java i.4 o superiore:

frame.setLocationRelativeTo(null);

altrimenti devi ricavarti le dimensioni dello schermo e centrare il frame in base alle sue dimensioni.