On the channels menu, click the envelope icon in the lower right-hand corner, then click the button to create a new message. The address book is the one on the far right, when you click that it will show your friend code on the cover. Click "register" to add friends either by email or by friend code. Once you have registered a friend, the address book will no longer automatically show the cover (this took me a little bit), to see it agian, press the "-" button on the Wiimote.
To send messages, go back to the send menu, and choose a message (the one in the middle, the envelope), choose the friend you want to send it to, and type your message. Any Mii you attatch will automatically go into their Mii collection.