There are two ways to accomplish this. First, navigate to the video list on the iPhone's iPod software. Drag your finger across a video's title from left to right and the red "Delete" button will appear, as if you were removing email messages. Tap it, and your video will be deleted.
The second method happens after watching a movie. Once it's done, you'll be presented with a dialog box asking if you want to remove the video to save space. Touch "Yes."
No need to carry "Saw II" around after you've watched it, right?