If Twitter wanted to run advertising on their site I believe they should follow the lead of Google and use highly-targeted text ads displayed down the right hand side of the page. If they were to put advertisements into the Tweet stream they would simply annoy the users, as it would disrupt the flow of information. But placing ads based upon tweets they have just sent, or that their followers have just sent, could get a decent click-through rate.
Also, they could probably do well to combine it with the Trending Topics that are highlighted on the front page. If many people are tweeting about Topshop, for example, they could put discreet text-only ads about clothing or something related onto the side bar.
This is just off the top of my head and I have not put much more thought into it than this, but it would probably be the least annoying method of displaying advertisements to users and potentially making a profit from it.
As much as I dislike advertisements, I do understand that they are where a lot of the money is on the Internet and any company the size of theirs needs to seriously consider them.
One other potential method could be to provide "Twitter appliances" similar to Google's so that companies can have their own private Twitter networks, but this may be harder to make a profit with as there are many microblogging platforms already available for free such as Laconica.
