I have built a package based on icedtea for Ubuntu and Debian.
You can apt-get it from
deb http://people.debian.org/~mkoch/java/ ./
Its currently very raw. E.g. it builds with GCJ but has wrong build
dependencies for it. And its only buildable for i386 currently.
Patches are welcome.
Please test and report back.