I had a freshly installed Ubuntu system and wanted to use gst-launch with x264enc, but it wasn't installed. Searching was proving hard, so in case others have the same problem, you need to install the gstreamer0.10-plugins-ugly-multiverse package.
e.g.:
sudo aptitude install gstreamer0.10-plugins-ugly-multiverse