I've noticed that some recent tweets have media associated with them, for example photos from TwitPic or Flickr and videos from Youtube. You can see them on the Twitter website directly, so it's more than just a link. My thinking is that Twitter has formed these partnerships with these select suppliers of media, being Flickr, Twitpic and such.
I'm looking to automate some tweeting from an image gallery. Yet, I do not wish to upload these photos to another place. I want to host them myself and then embed/refer to them from a tweet. Yet, they should also be seen inline.
Is such a thing possible?
2017 edit: Looks like you can get a media_id via POST media/upload and then pass the id into POST statuses/update.
2014 edit: You can add media to tweets using POST statuses/update_with_media.
Original 2011 answer: No, you can't embed media into a tweet, nor can you upload photos to Twitter.
The "embedded" media you see is just Twitter scraping the URL for the photo or video, and showing it directly within Twitter, saving users from needing to click on the link to view the media. And Twitter only scrapes media for certain popular sites.
If you want Twitter.com users to see your images inline, you'll need to upload images to one of the popular image sites you mentioned, and have its URL in your tweet.
If you still want to drive traffic to your site, you could also include your gallery's URL within the same tweet.
But keep in mind that not everyone uses Twitter via Twitter.com; there are a plethora of Twitter clients available, and I doubt many feature inline media scraping.
I'd suggest just linking to your gallery/images, and not worry about uploading them elsewhere.