When is an object eligible for garbage collection?

An object is eligible for garbage collection when there are no more root set of references to that object. References that are held in a variable are usually dropped when the variable goes out of scope.
 

What are root set of references? The object references in the local variables, operand stack of any stack frame and any object references in any class variables , and object references that were passed to native methods that either haven't been "released" by the native method.

In Reference Objects and Garbage Collection:

An executing Java program consists of a set of threads, each of which is actively executing a set of methods (one having called the next). Each of these methods can have arguments or local variables that are references to objects. These references are said to belong to a root set of references that are immediately accessible to the program. Other references in the root set include static reference variables defined in loaded classes, and references registered through the Java Native Interface (JNI) API.
All objects referenced by this root set of references are said to be reachable by the program in its current state and must not be collected. Also, those objects might contain references to still other objects, which are also reachable, and so on.

In Garbage Collection:

The root set in a Java virtual machine is implementation dependent, but would always include any object references in the local variables and operand stack of any stack frame and any object references in any class variables. Another source of roots are any object references, such as strings, in the constant pool of loaded classes. The constant pool of a loaded class may refer to strings stored on the heap, such as the class name, superclass name, superinterface names, field names, field signatures, method names, and method signatures. Another source of roots may be any object references that were passed to native methods that either haven't been "released" by the native method. (Depending upon the native method interface, a native method may be able to release references by simply returning, by explicitly invoking a call back that releases passed references, or some combination of both.) Another potential source of roots is any part of the Java virtual machine's runtime data areas that are allocated from the garbage-collected heap. For example, the class data in the method area itself could be placed on the garbage-collected heap in some implementations, allowing the same garbage collection algorithm that frees objects to detect and unload unreferenced classes.