It appears that Verizon and AT&T are serious about not wanting you to use your current data plan for tethering, as they have blocked access to popular applications that enable it on the Android Market. There's a bit of conflicting information out there, as a few other sites have reported that all carriers, or that other carriers have done the same. We've found that T-Mobile and Sprint haven't blocked them, but Verizon and AT&T have, as shown in the image above.
It's no big surprise. To your carrier, tethering is something you are supposed to pay extra for, and that's in the agreement you signed. Using apps like PdaNet goes against that agreement, and they have every right to block them. Even if we don't much like it. It's their service after all, we're just lowly users.
The good news is that they can't block sideloading. You can certainly find those same apps at the developer's website(s), and download them and install easily. On a Verizon phone, just save it to your SD card and install from there, on an AT&T phone use the Sideload Wonder Machine and you'll be fixed right up. There's also native tethering built into Android 2.2 and higher, as well as USB modem functions on many phones, built right into the OS. And of course, if you root and hack at it, anything is possible on most any phone. The option is still out there, it's just not quite as easy.
Update: As several have mentioned, it's quite possible to keep carriers from meddling with your Android Market experience. If you have an AT&T phone, you can pop the SIM card out and use Wifi to browse the Market; and enabling Airplane Mode, then turning on Wifi works for both AT&T and Verizon phones.
More information here: Android Central forums Thanks, John, and everyone else who sent this in!