To get 256 colors for Emacs running inside your xterm (emacs -nw), follow these instructions:

  1. make sure you have the ncurses-term package installed
  2. place the following in your ~/.Xdefaults file: XTerm*termName: xterm-256color
  3. run the following command from your command line: xrdb -merge ~/.Xdefaults
  4. open a new xterm and run emacs -nw

To check how many your terminal is supposed to handle, run tput colors on the command line.

More info available from twb’s Terminal Emulator 256 Color Support page. (Dead link, but the one in twb's user page still works.)