As the name implies, TinyVM is indeed a small Java Virtual Machine that is downloaded to the RCX to replace the standard firmware. Java programs are then written and byte-compiled on the PC and downloaded to the RCX. A TinyVM program can use some standard Java libraries, and a library for control of sensors, motors, and such on the Mindstorm is provided. TinyVM requires an already functional java compiler.
leJOS is a similar project (in fact, it is a code fork) by the same author. It is much higher footprint (currently about 5K additional size) but also includes substantial additional functionality, including support for floating point and String constants. Other planned features include garbage collection and multiple program loading.