Having them play together nicely especially over a ssh connection from another box can be really annoying. I spent quite some time to figure out a nice working setup which isn't too hackish (like setting TERM=xterm-color or so..)
I write a howto over at forums.freebsd.org so have a look there too. Here is the short version.
You will need a $HOME/.termcap file containing this:
rxvt-256color|rxvt-256color terminal (X Window System):
:tc=rxvt-unicode:
:tc=rxvt:
In your shell rc file (e.g. .bashrc) add something like this for screen:
if [ -f ${HOME}/.termcap ]; then
TERMCAP=$(< ${HOME}/.termcap)
export TERMCAP
fi
Finally tell screen what to do in your .screenrc file (all in one line):
termcapinfo xterm-color|xterm-16color|xterm-88color|xterm-256color|rxvt*
'Co#256:AB=\E[48;5;%dm:AF=\E[38;5;%dm'
Still doesn't work? Don't blame me. :)
(Check if your programs were compiled properly with 256 color support)