You should be able to connect to AIm just having the phone. I think the AIM messenger is under the IM category within the phone.
I think it also varies how much it costs to log on and off...at least for cingular, the representative told me they charge how ever much K's it takes to download to open AIm...however i've heard otherwise that it could just take a text message to log on.