The bad news is that Skype for Windows Mobile is no longer available for download. But, the good news is Skype now runs on Nokia Symbian phones.
You can download the application by visiting skype.com/m on your mobile phone. It will install automatically. I've tested the application on Nokia E63 and it works great.