I've used Skype on my mobile phone as well. My phone will use WiFi if available but I have unlimited data plan too so it doesnt really matter.
Just be sure to check the processor that your phone has. I have the cingular 8125 (an HTC phone) and its a bit underpowered for Skype (even compared to other HTC phones). Most windows mobile phones will run skype fine. - Dave
