While looking at the message index you can view the sender's email address by pressing the @ key. On the status line at the bottom of the screen you should see the sender's complete email address. Hit `a' to add that sender to your address book. You will be asked to confirm the name and email address of the sender (which is a great time to modify it for your own purposes if you'd like to do so).
In the context of more complicated programs that integrate the address book with other software (like instant messaging clients: Kontact/Kmail/Kopete on Linux and Addressbook/Ichat/Mail on Apple Mac OS X), the rudimentary mutt address book is somewhat of a disappointment. It is simply a text file containing a list of names and email addresses organized by aliases (nicknames) that you assign them. Each entry, one per line looks like this:
alias randall_wood Randall Wood <rwood@therandymon.com> alias dogcito Dogcito and Oso <dogcito@zafiro.com>
You can add additional entries as described above, edit the text file directly any way you like, or try integrating an add-on address book with a bit more functionality. In section 3.5 I'll discuss how to configure the mutt address book, and in 3.5.2 below I'll discuss how to interface with more powerful address book components.