Check out the IM video on this page
http://androidcommunity.com/android-...emos-20080913/
[ame]http://www.youtube.com/watch?v=slDZgB-IvJc[/ame]
It shows that you could log onto GTalk, AIM, MSN and Yahoo messengers from the IM client in Android. And IIRC from earlier previews of Android on Google 10 conference earlier this year, it showed that the IM client can run in the background and provide notifications of any IMs received while you were using other apps. And since it runs in the background, it'll could also be on 24/7.
And I'm sure it'll use the cell data network but not sure about the per message charges though. Although, since IM messages are normally routed through servers that belong to respective IM networks (such as Google, Yahoo or Microsoft), I'm not sure how T-Mobile would implement a per-message charging system even if it wanted to (probably if they talk to each of those companies, but I don't think that'll be the case).