Depending on the version of the Microsoft Exchange server that you would like to connect to it is required to make sure that an additional package is installed that provides this functionality.

For Microsoft Exchange 2000 and 2003 (and possibly earlier versions of Exchange that use Outlook Web Access) it is recommended to use the package evolution-exchange.

For Microsoft Exchange 2007 and 2010 (and possibly earlier versions that support MAPI) it is recommended to use the package evolution-mapi.

For Microsoft Exchange 2007 and 2010 the package evolution-ews is currently under development and will replace evolution-mapi in the future. It might not be available yet for your distribution.