Make sure that your `$TERM` is set correctly before running Emacs.

If launching direct from the terminal, check with `echo $TERM` - preferably its value would be `xterm-256color`

Set it either directly before you run Emacs:

    TERM=xterm-256color emacs -nw 

With any other arguments you need.

As a more permanent solution, set `$TERM` in your shell profile, e.g. `.bashrc` or `.zshenv` (depending on your shell)

    export TERM=xterm-256color

If you are running Emacs in a GNU Screen session, use `screen-256color` as the value of `$TERM` instead.