Before installing Java, I upgraded the Linux kernel to 3.4.29+ and Ubuntu following the steps described on the pcDuino 04-04-2013 update page.
Download the JRE (ejre-7u21-fcs-b11-linux-arm-vfp-client_headful-04_apr_2013.gz) from http://www.oracle.com/technetwork/java/embedded/downloads/javase/index.html. If you have a screen, keyboard, and mouse connected to your pcDuino, you can dowload directly to the device. I am using SSH to access my pcDuino, so I downloaded the file to my Windows desktop and used WinSCP to transfer the file to the pcDuino.
At the pcDuino command prompt, run the following commands to extract the JRE:
tar xfv ejre-7u21-fcs-b11-linux-arm-vfp-client_headful-04_apr_2013
The JRE is now located in a subdirectory called ejre1.7.0_21. Note the full path for this directory.
Add the following lines to your account's .bashrc directory (changing the path to the JRE directory path noted in the last step).
This version of Java uses "soft float, so install the required libraries using this command -
sudo apt-get install -y libc6-armel libsfgcc1
Log out and then log back in so the new environment variables take effect. Confirm that Java runtime now works by running java -version.