In addition to http://notmuchmail.org/emacstips/#index11h2
and Jani's 'goobook' in id:"87zkfuh3i0.fsf@nikula.org"
you can now also use

http://www.iki.fi/too/nottoomuch/nottoomuch-addresses.pl 

for your address completion needs when composing mail/reply.

This program is 1) easy to install and 2) pretty fast to use
when completing.

How to install

1) Download the program from above url on the machine you're running
   notmuch and find suitable location to it.

2) Verify it's sha1 checksum is 125f3917b3f2dc68bdf30af04ab623d53321e50c

3) chmod 755 /path/to/nottoomuch-addresses.pl

4) Run  /path/to/nottoomuch-addresses.pl --update
   When run first time this gathers email addresses from all of your mail.
   This may take a long while to complete -- depends on the amount of email
   you have. Further --updates are much faster as those just take addresses
   from new mail.

5) Test that it works: Run  /path/to/nottoomuch-addresses.pl notmuchmail

6) In case you're using emacs mua with notmuch, edit your notmuch
   configuration for emacs with the following content:

   (require 'notmuch-address)
   (setq notmuch-address-command "/path/to/nottoomuch-addresses.pl")
   (notmuch-address-message-insinuate)

7) Restart emacs notmuch mua (or eval above lines) and start composing
   new mail. When adding recipient to To: field. press <TAB> after 3
   or more characters have been added. In case you get 2 or more address
   matches, use arrow keys in minibuffer to choose desired recipient...

8) Enjoy!

/path/to/nottoomuch-addresses.pl --help  provides more detailed information.

BR,
Tomi