The tethering settings are located in Settings > General > Network > Internet Tethering. Initially is said I have to contact my carrie to enable it, but it works now.
As for recording video, you still have to as an app like Cycorder.
It should be there. There was a carrier update for me in iTunes. Maybe that enabled it? I know there is still some controversy regarding carriers allowing tethering. I'm with Rogers.