Skype today released the first Beta of Skype for Mobile, which allows users of most new mobile phones to run a version of Skype on their phone.  The Beta allows you to:

Send messages to your contacts
Receive calls from Skype contacts (charged at SkypeOut rates)
Make calls to Skype contacts if you live in Brazil, Denmark, Estonia, [...]