I don't think this is possible to do automatically, and actually, I consider this situation to be desirable. Not to sound anti-social, but I don't want everyone I Email to be automatically added to my contact list, and if I were sending an Email to a large of group of people, I expect I'd get annoyed at having to wait for Evolution to inspect the entire recipient list and compare it to my existing set of contacts, then ask me what to do about each person who wasn't found. Bleh.
The simplest way I know of to add a contact is to just right-click the person's Email address. A window will pop up with an option to "Add to Contacts". Click it and you're done. -- J.W.