There are two broad categories of GC algorithms: 1) reference counting, and 2) "mark and sweep."
Reference counting is what it sounds like: for every object, you keep a count of how many times it is referenced inside the object itself. Every assignment to a reference variable has to include code to increment or decrement these counts. When a count reached zero, an object can be collected. Although this sounds simple, it actually has some important problems, the worst of which is that "cycles" -- two objects each referencing each other -- will prevent objects from being collected. It also uses lots of extra memory, and because assignments become so complicated, it's actually quite slow.
In a mark and sweep algorithm, the collector periodically starts at the "roots" of memory (stack frames of all threads, static fields) and marks every object that can be reached. When it is through, unmarked objects are unreachable and can be collected. This technique isn't fooled by reference cycles, needs only one extra bit of memory per object for the mark, and adds no overhead to other operations.
All Java garbage collectors are based on some kind of mark and sweep algorithm. In general, Java uses "generational" collectors, in which the heap is divided into "generations"; objects that have been around a long time are moved into generations that are examined only infrequently by the GC. It has been observed that most brand-new objects are garbage-collected very soon; the longer an object exists, the less likely it is that it will ever need to be collected.
Well, it couldn't be simpler to implement. Every time an assignment is made to a reference variable, you increment and decrement the counter(s) for the referenced object(s). When you find an object has a count of zero, you decrement the counts of all the objects it holds as fields, and then delete the object. If, when decrementing the field objects, you find more zeros, then you continue to do the whole thing recursively, as long as necessary.
You obviously can't implement this in Java for Java objects, not transparently, anyway. It has to be part of the underlying language machinery. Are you implementing your own JVM? If so, then you'd want to hook this into the code for all the "store" bytecodes, putfield, etc.