The reason you can't find Skype in the Market is that you aren't on Verizon. That's right - Verizon somehow convinced Skype to sign a deal with the devil - and so Skype apparently is only available to Verizon Android phones. And to make things worse, Skype ONLY functions over 3G - not Wi-fi.
As you can tell, I'm a little ticked off that the Skype chose to go this route, and I'm even on Verizon. Last time I traveled to Europe, I took my Verizon WinMo phone, Samsung i730 and used it to call the U.S. using Skype via wifi. Guess that won't work now.
The only good part of the Verizon/Skype product, is that you can call internationally now using Skype and it is on the 3g network, which can be a good thing - it is just a pity you can't choose to use it on wi-fi instead.