How to enable automatic word-wrap when composing messages?
Starting from No Gnus, automatic word-wrap is already enabled by default, see the variable message-fill-column.
For other versions of Gnus, say
(unless (boundp 'message-fill-column) (add-hook 'message-mode-hook (lambda () (setq fill-column 72) (turn-on-auto-fill))))
in ~/.gnus.el.
You can reformat a paragraph by hitting M-q (as usual).