How can I run Selenium tests on an Ubuntu server?

Try this for automating headless server stuff. (Caveat, I wrote the post below)

http://www.semicomplete.com/blog/geekery/headless-wrapper-for-ephemeral-xservers.html

Basic summary is I made a script to run any command within a newly-created headless X server. This also lets you run lots of headless X servers at a time if you need to.

So for starting selenium-rc in a new headless X server, you would do (using the tool described in the above post)

sh ephemeral-x.sh -x "Xvfb -ac -screen 0 1024x768x24" java -jar selenium-server.jar ...

i haven't tested it by myself, but this sounds promising:
http://www.alittlemadness.com/2008/03/05/running-selenium-headless/

i will try this for myself.

EDIT:
finally i had time to test for myself. i tested it on suse, but should be the same for ubuntu, except perhaps package and path names.

first install xvfb package, on suse it is called xorg-x11-Xvfb

start xvfb in background with display, screen and resolution parameters:
/usr/X11R6/bin/Xvfb :15 -ac -screen 0 1024x768x8 &

change your display settings:
export DISPLAY=localhost:15.0

and start your selenium rc:
/opt/java/bin/java -jar selenium-server.jar > /var/log/se_rc_server.log 2>&1 &

you could also start selenium rc with a testsuite specified:
/opt/java/bin/java -jar selenium-server.jar -htmlSuite "*firefox3" "http://www.google.com" "/root/google.ts.html" "/root/google_report.html"