1. Ensure that Terminal declares itself as "xterm-256color"
Under Terminal > Preferences... > (Profile) > Advanced, "Declare terminal as:" should be set to xterm-256color
.
2. Build a version of screen that supports 256 colors
This is easy with homebrew:
brew install screen