From section 3.1 of the evil-mode manual (PDF)

(evil-define-key 'normal foo-mode-map "w" 'bar)

For example I did this:

(evil-define-key 'normal org-mode-map (kbd "TAB") 'org-cycle)

To make tab work properly to expand entries in org files in console mode (emacsclient -nw).