The answer is technically neither. According to the Java Virtual Machine Specification, the area for storing string literals is in the runtime constant pool. The runtime constant pool memory area is allocated on a per-class or per-interface basis, so it's not tied to any object instances at all. The runtime constant pool is a subset of the method area which "stores per-class structures such as the runtime constant pool, field and method data, and the code for methods and constructors, including the special methods used in class and instance initialization and interface type initialization". The VM spec says that although the method area is logically part of the heap, it doesn't dictate that memory allocated in the method area be subject to garbage collection or other behaviors that would be associated with normal data structures allocated to the heap.

----------------------------------------------
|        Heap         | String Constant Pool |
|---------------------|-----------------------                      
|                     |                      |
|    "abc"  "abc"     |       "abc"          |
|      ^      ^       |                      |
|      |      |       |                      |
|     s1     s2       |                      |

As Andy Turner said, the new operator always produces a new instance. It is guaranteed by the JLS.

The only small wrinkle is that under certain circumstances (e.g. if escape analysis is enabled in certain JVM versions) the new operator might allocate an object on the stack rather than the heap.