Both OpenJDK and GCJ are available for install on Debian, and now I wonder what's happening. Don't these provide same functionality?
Debian's stance is that, beyond certain critical system components which are considered required¹, there is no preferred software. If two programs provide similar functionality, and they're both suitable for Debian², and there's a Debian developer willing to maintain each package, then both programs will end up in Debian. The idea is that it's up to the user to choose which program to use.
On a given system, at most one Java implementation can be
Or at least strongly advised.
They are fine with both for the most part: OpenJDK is installed by default on supported platforms, otherwise GCJ will be used instead.