new Object { } Construct

You would use the second construct in the case that you want to make an anonymous class. if you have a method that takes a callback as an argument, you might want to specify the implementation of the callback inline as opposed to giving it a name and putting it in a separate file or declaring it elsewhere in the same file.

There's also a trick called double brace initialization where you can get around not having syntax for literal maps and lists by using anonymous classes, like this:

Map map = new HashMap() {{put("foo", 1); put("bar", 2);}};

Here the nested braces create an instance initializer. The object bound to map is not a HashMap, its class is an anonymous class extending HashMap. (That means if you have a PMD rule about classes needing to declare serial uids then it will complain about this.)

Double-brace initialization is a fun trick to know but don't use it in real code. It's not safe to pass around the map created like this, because the inner object keeps a reference to the outer instance so if anything in the program holds onto a reference to the map it keeps the outer object from getting garbage-collected. There are also problems with serialization.

As others have already said, it creates an instance of an anonymous class, subclassing Class. Here's an example how it is commonly used:

panel.addMouseListener(
  new MouseAdapter () {
    @Override
    public void mouseEntered(MouseEvent e) {
      System.out.println(e.toString());
    }
  }
);

The above code creates an instance of an anonymous class which extends MouseAdapter. In the anonymous class the method mouseEntered has been overridden to demonstrate that the anonymous class works basically as any other class. This is very convenient and common way to create (usually simple) listeners.

This construct makes actually two things: 1) It declares an anonymous class which extends the class you use in the constructor and 2) creates an instance of this anonymous class.

Edit: When using such a construct you can observe the anonymous class by looking at the generated .class files. There is the normal MyClass.class file and another one for each anonymous subclass: MyClass$1.class for the first and so on.