Currently they do have to be hosted somewhere else. YouTube is obviously the most popular, but site does support some of the other, smaller sites.
When you find a video you want to embed in a message, just take the URL and put it right in the body of the message. No special tags or characters are needed. Then it will bring up a small window when you post the video for other people to view it right in your message.