I'd like to further elaborate on this just to help out if you don't mind ^^
As was already said: bottom right corner, message board icon
Second: create message, even if you're not sending one this time
Address book to add Wii friends to your list
You can even add email and cellphone numbers to your wii it seems, just pick Wii for now to add friends though
From here you cann see who has is already on your list, the darkened names have added you to their list as well, just hit register to add new Wiis to your list, you don't have to attach a Mii to a name in your address book, it's completely optional.
Hopefully this'll help new Wii owners and future Wii owners with that feature of the Wii.