So, I'm trying to add /usr/java/bin and /usr/java/jre/bin to my path. I've edited /etc/profile, so it looks like this:

# /etc/profile: system-wide .profile file for the Bourne shell (sh(1))
# and Bourne compatible shells (bash(1), ksh(1), ash(1), ...).

if [ "`id -u`" -eq 0 ]; then
PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/bin/X11"
else
PATH="/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/games:/usr/java/bin:/usr/java/jre/bin"
fi

if [ "$PS1" ]; then
if [ "$BASH" ]; then
PS1='\u@\h:\w\$ '
else
if [ "`id -u`" -eq 0 ]; then
PS1='# '
else
PS1='$ '
fi
fi
fi

export PATH

umask 022

However, when I echo $PATH, I get:
/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/games
which is obviously missing what I added.
Shell is /bin/bash, and modifying .bash_profile in my user directory doesn't seem to do anything either... any ideas what's up?

Are you making sure to log out? Changes won't take effect until you do.

Yeah, I log out and back in and nothing changes. My /etc/profile has been like that for weeks actually, but I still don't have the appropriate path.

I have the same problem...

do something like
rgrep "<part of your $PATH variable that seems default>" /etc

for me it matches
/etc/kde3/kdm/kdmrc:# Default is "/usr/local/bin:/usr/bin:/bin:/usr/X11R6/bin:/usr/games"

I guess by setting the UserPath in that file, it might work...
Also, it seems to me that /etc/profile works if you login outside X...

look for files .bashrc .bash_profile .profile in your home folder. they override system wide settings for a user.

I at one stage had the same problem, however there are two really great tutorials (one of which from memory is by Sun) freely available on the net. I don't have the addresses on hand, but I'm sure a quick trip to google searching for 'installing java linux' will yield more than enough results. They helped me out no end.