if you are trying to save an embedded video, then the firefox plugin flashgot will almost definitely be able to handle it as well. for the few exceptions, recordMyDesktop is the way to go.
in order to configure recordMyDesktop to handle high quality video and your computer's internal audio, there are a few options you'll need to use. firstly, install gtk-recordmydesktop (or qt-recordmydesktop, if you're using kde). then, assuming that you're using a distro with pulse audio, install pulse audio volume control (pavucontrol) as well. open up gtk-recordmydesktop, click "advanced", head to the sound tab, and replace the device name (it should be "DEFAULT") with "pulse". then, if you want decent sound quality, set it to record 2 channels instead of one and set the frequency to upwards of 30-40kHz (a high quality mp3 is usually around 44). make sure you increase the frame rate under the "performance" tab as well, or your result will look awful. next, try a test recording. if your computer doesn't explode, then hopefully it will be able to handle recording while video is playing.
next up is to set it to record the internal sounds of your computer rather than recording from a microphone. this is what you'll need pulse audio volume control for. fire it up, click on the "recording" tab, and then tell recordmydesktop to start recording again. it should then appear under the "recording" tab with "built in audio analog stereo", or something similar to the right of it. click on that and switch it to "monitor of ...", and it should then be recording every sound played through pulse on your computer, including those from whatever video you're trying to record.