This is what you do:
Step 1: While playing in the game, in console type /record nameofdemo. A big red dot, like on a video camera should appear in the top right corner of your screen.
Step 2: When finished recording go back into console and type /stoprecord
Step 3: Go back to the main menu of Tremulous
Step 4: Type /demo nameofvideo <- the recording you just took should start playing
Step 5: When it starts playing, put down the console and type /video videonamehere <- this creates you video
While the demo is playing, try not to press random keys except the ~ key to bring down console. If you do this, the demo will stop playing and you will be back at the main menu.
Step 6: Then, if you are using Windows, go to C:/Documents and Settings/username/Local Settings/Application Data/Tremulous/base/videos
The folder in italics is a hidden folder, to see it go to Tools -> Folder Options -> View -> then select the option that says Show Hidden Files and Folders
Mac and linux directions to come but i doubt you would need them