From within Outlook
Go into the Evercontact toolbar and then click the "Update" button:
(for Outlook 2007, go to Tools>Evercontact and then click "update".)
*****NOTE******
If you run into the error message "there is an error with this Windows Installer Package. A program required for this install to complete could not be run" then you'll need to download Microsoft's tool here and then install using that tool.
From a direct download link
Download the latest version of the Evercontact add-in for Outlook here.
Once it's downloaded, make sure to close Outlook before installing.