I use universal IM clients for both my PC and my Android phone. I'm running Digsby on my PC and the Trillian client on my Android.
I'm not specifically attached to either piece of software, they're just what's worked for me so far. I do however have an annoyance in that I will receive messages on both my phone and my PC at once. What I really want to be able to do is only have the messages on my PC when I am on my PC, then only have messages on my phone when I'm wandering about.
Has anyone tried to solve a similar problem?