I recently switched to Mac. I was previously using Outlook Express (OE). In OE, click File, Export, then Address Book... Save as a text file, aka delimited or comma separated values. The file will end with .csv or .txt. Mac will read these no problem. Just Import... from your new email client.
As for messages, the new mail client on the Mac (Mail or Entourage, maybe?) will import these from the server. If there are some messages only on your hard disk, you could forward them to an email address again or... I think you might be able to Import... these as well from the Mac mail client. You could also copy the files straight from disk to disk.