You have two options for tethering. Neither of which is illegal, despite what you may have heard.
Option 1: - pay Verizon $20/month for tethering with a 2GB cap. Because Verizon cannot tell what data is tethered and what isn't, anytime you have the tethering app turned on, even if you're downloading the data directly on the phone, the data used will count towards your 2GB cap.
Option 2: - tether outside of Verizon's service, using data that you already paid for. However, this is against their terms of service and thus, a violation of the contract that you signed with them. While not illegal, you can have your service adversely affected if caught. With that said, unless you walk into a Verizon store and tell them you're doing it, you won't get caught. Verizon has no way of telling when you are tethering outside of their service.
Option 2 has further suboptions. You can get a free app for tethering, which requires root access. Or, you can purchase certain apps, such as PDANet, that don't require root access. Finally, you can change the DUN address on the phone which allows you to enable the tethering app on the phone without Verizon having a clue of what you're doing.