However, most obfuscators will intentionally scramble the class, method and field names so it isn't obvious what they do. Additionally, they do their best to make them all conflicting. For example having two methods in the same class with the signature "void test()" and "String test()" is illegal in Java source. However it isn't in the binary class files. Obfuscators will tend to use this fact to break the decompiled source code.
The only thing they have to be careful about is method overriding; if a method with exactly the same name/return type/arguments matches one in a superclass or interface, you're guaranteed it is an overridden method, even in an obfuscated file.
Most decompilers do not fix this issue; you end up with some nice java source, but unfortunately with many conflicting method, field, and class names. Enter jrename: This takes a set of binary .class files, analyses and fixes the names of them and their members, and spits out a second set of processed .class files. You can then run these through a decompiler with hopefully zero errors caused by illegal names.
After that, you load it into Eclipse, and start figuring out what methods do what. Eclipse has some very nice code refactoring features, so you can use those to rename methods/fields/classes as you determine what they are and have them globally affect any uses across the rest of the source.
Jrename's source is here, and there's a binary release here. It uses the extremely cool ASM library for all binary class file access.
Incidentally, the "NeedsRenamed()" method is pulled pretty much exactly from another Java deobfuscator project, JDO, which is written in C#. I decided to write my own from scratch in Java as I wanted to be able to modify the deobfuscator easily: I found the code in JDO rather more complex than I felt it had to be, and maintaining a complete Java .class file parser also seemed an unnecessary overhead, given the existence of ASM. I also felt writing it in Java was more suitable than C#, and I wanted a simple command line interface, not a GUI.
Don't get me wrong though, I much prefer C# coding to Java coding!