Emoticons are stored in the AppData folder under your Windows account. For example, if you are on Windows Vista/7, given that your account name on Windows is "Vivien" and that your Windows Live ID is "firstname.lastname@example.org", the emoticons should live in this folder:
Now copy this folder from Machine A and paste it into the same named folder and path on Machine B. Restart Windows Live Messenger on Machine B, and you should now see all your emoticons on Machine B!
Note that the AppData folder is hidden by default. The simplest way to get to the folder is by typing in the path directly to your Windows start menu search pane. If you prefer browsing to the folder via Windows Explorer and you're having trouble finding the AppData folder, make sure to show all hidden folders.