Yes, you can, however java requires a lot of free RAM (memory) to create java virtual machine. So it may not work on smaller vps plans. Example error message on a cpanel based Freedom plan vps:
root@vps [/usr/java/jre1.5.0/bin]# /usr/java/jre1.5.0/bin/java
Error occurred during initialization of VM
Could not reserve enough space for object heap
Could not create the Java virtual machine.
As you can see the vps does not have enough free memory to create JVM. An Enterprise level vps plan may be able to use java, but again it depends on how the memory is being used already in other programs e.g. cpanel, apache, mysql etc.