Under Terminal > Preferences... > (Profile) > Advanced, "Declare terminal as:" should be set to xterm-256color.
This is easy with homebrew:
brew install screen
When this finishes you'll have a new binary in /usr/local/bin/screen.
Add /usr/local/bin to the front of your $PATH so that your shell uses this binary, and not the one in /usr/bin (you can confirm that it's using the correct one with which screen). If you're using the bash, this goes into your .bash_profile:
PATH="/usr/local/bin:$PATH"
If you're using another shell, then you probably already know where this goes. :)
Something worth noting is that bash will hash the path that commands resolve to. You can see this when running
type screen. If you just installed screen you may need to runhash -d screento clear screen from bashes path resolution hash. Alternatively, close your session and open a new bash instance.