You've just started using a brand-new Mac. You launch Mail.app and start to compose an email to a friend. That's when it hits you: You haven't yet sent any messages on the new machine, so Mail.app hasn't had any addresses to remember, so it can't autocomplete your friend's address when you begin to type his name. Drat! Fortunately, as Marco Arment recently blogged, there's a way to copy Mail.app's autocomplete database from your old setup to your new one. (Marco also happens to be the developer of Macworld favorite Instapaper.)
On the original Mac--the one that successfully autocompletes email addresses for you--use the Finder to go to the folder ~/Library/Application Support/AddressBook/. (If you wish, you can select and copy that path here, then go back to the Finder, choose Go -> Go To Folder or type Shift-Command-G, and paste the path.)
In that folder, you'll see a document called MailRecents-v4.abcdmr. That file contains the goods! Copy it from your old Mac to your new one through any means you'd like. (If you want to get particularly meta, you could even email it to yourself.)
On the new Mac, navigate to that same ~/Library/Application Support/AddressBook/ folder in the Finder, and drag the file you copied into it. (Replace the file that's already there if prompted to do so.) When you relaunch Mail on the new Mac, all of your autocomplete entries should be restored.