BarnOwl has built-in support for 256-color terminals, assuming your libncursesw (and GNU Screen, if you're using it) support it.

Outside of screen, your TERM environment variable must be set to xterm-256color instead of xterm. If you're running BarnOwl out of the locker, the barnowl-256color wrapper sets this for you. But to get 256 color support for all programs, put something like this in your ~/.bashrc:

case "$TERM" in
    xterm) TERM=xterm-256color;;
esac

As of Debian Lenny, the stock screen is built with 256 color support. To enable it, first make sure your outer TERM is xterm-256color as above, and add the following to your ~/.screenrc:

# Erase background with current bg color
defbce on
# Advertise 256 color support to inner applications
term screen-256color-bce

(If for some reason you do not want to set your outer TERM to xterm-256color, you can teach screen how to use 256 colors anyway by ​adding: termcapinfo xterm 'Co#256:AB=\E[48;5;%dm:AF=\E[38;5;%dm')

For older platforms, the barnowl locker may have a newer screen under the name of screen-256color; /mit/barnowl/etc/screenrc includes the aforementioned additions.

In case you want to use 256-color Emacs inside screen, see ​Emacs bug 2650. (If you use a light-background terminal, you may also want to customize frame-background-mode to light.)