It's pretty trivial for Verizon to detect that you're tethering traffic. Between the user agent on your PC's browser, the TCP settings your OS uses, the content you download, the websites you visit and a host of other things Verizon can easily flag you as using tethering. So far they've looked the other way, but there's no guarantee they will continue which is why I spring for the $20/month. Some examples:
User agent:
Many Android browsers can spoof a desktop user agent, so this is not deterministic but it's easy to use it to flag your account for further review. Plus the list of user agents browsers typically use is fairly small, SkyFire in Desktop mode claims to be "Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_5_7; en-us) AppleWebKit/530.17 (KHTML, like Gecko) Version/4.0 Safari/530.17" but most people would probably have updated to at least 10.6 and many would be using Firefox. Now you can always copy and paste the string and spoof your desktop browser to look like a mobile browser, but that can get annoying and produce interesting results.
In addition to the browser, I'm pretty sure Flash has its own user agent that is much harder to spoof.
TCP settings:
Each OS has its own set of default parameters and window scaling algorithms. PCs are designed to work on fast broadband connections, phones on unreliable wireless connections. Based on the TCP parameters your computer advertises this could be a surefire way of knowing that you're not originating traffic from your phone.
Content:
Want to watch a NetFlix movie? Hulu content? Listen to Blip.fm? You can't do a lot of things from the phone that you wouldn't think twice about on a PC.
Sites:
How often does your computer poll updates.microsoft.com? us.archive.ubuntu.com? Whatever the Mac equivalent is? Do you use an OS-specific time server? Again, all pretty decent alerts that you've got something behind your phone.
Facebook
Twitter
Instagram