If you're using Outlook Express, I don't think it uses rich text, you'll have to use HTML (which should work with smileys anyway). Click Tools, Options then choose the Send tab. Check the button beside HTML as the mail sending format.
If you're using Outlook, Click Tools, Options and choose the Mail Format tab. Set Rich Text in the drop-down box named "Compose in this message format:"
If you're using Thunderbird, click Tools, Account Settings, then under your account in the left hand pane, click on "Composition & Addressing" and click the "Compose messages in HTML" box.