How can a shell script tell if it is running in an xterm window with 256-color support?
You can check for xterm version - $XTERM_VERSION. Though I am not sure from which version xterm started to support 256 colors. Other terminals (for example gnome-terminal), behave similarly to xterm but also set COLORTERM variable to correct terminal name (gnome-256color).
Since most xterm-s are colorized these days, I would assume that the terminal has 256 colors, and make the script accept an option (perhaps -monochrome or -no-colors) otherwise.
BTW, I also see a reason for some power-user to force the -monochrome behavior: on very slow connections (think of intercontinental ssh) it might be useful to disable colors to lower the bandwidth.