Java is a different kind of interpreted language. Most interpreters interpret line by line java is more like a real program where the whole program is compile into an executable called pico code. The virtual machine then executes the compiled pico code, verses a line of code. So the virtual machine is acting more like a computer/operating system than an interpreter (kind of line the pc virtual machines we seen). It is because of this feature, IBM was able to create a JIT compiler that directly maps java pico code to native machine code.
The reason why most java runs the same everywhere is because everybody prior to Android used the same virtual machine layout. Android decided to go with a different binary layout known as the Dalvik virtual machine. They obviously said not care for compatibility issues because they whet providing different environment that traditional java.
For more info see the wiki Http://en.wikipedia.org/wiki/Dalvik_(software)