Skype has been available on Verizon Android phones for a while now, but because of the exclusive deal between Verizon and Skype, it was limited to only that carrier. Now that wait is finally over and Skype is now available for every 2.1+ Android phone, regardless of carrier. In the US, you’ll be limited to Skype Calls using WiFi only though. Unfortunately it doesn’t support video chat either, and there’s no mention of future support for it.
You should be able to find it in the Android Market.
Source: Skype Blog via Neowin