Movie Making Manual/Sales and Exhibition/Putting Videos Online
MPEG4-AVC provides the most efficient compression compared to every other codec out there.
There are some opensource H.264 encoders (e.g. x264), and people have used them to successfully compress video, but they are buggy at present.
Probably the most cost effective way to produce H.264 is to use Apple Quicktime 7 Pro. The video really deteriorates below about 512kbps but 1Mbps is pretty nice.
Encoding H.264 Quick Times from Premiere Pro 
First, download the most recent version of Apple Quicktime.
Then take a look at Apple's H.264 encoding guide.
Beware: encoding H.264 using two passes on QT Pro 7.0.3 takes a long time (a 3 minute SD video took 2 hours to encode on an Athlon64 2.4GHz).
Problems setting datarate 
For some reason, if you try to use the Adobe Media Encoder from within Premiere Pro 1.5.1 then you can't set the datarate. So export from PPro as an uncompressed AVI, import into Quicktime 7 Pro, compress as MP4 and set as H.264. Or, alternatively, change the "export size". In premiere when you look at your transcode settings in the Media encoder, it is under the Video area. Underneath where you choose the video codec settings, you can tell the encoder a frame size.
- "Can't set bitrate when encoding QT H.264 using Adobe Media Encoder" thread on Creative Cow.
Gamma problems 
RGB movies can look washed out when converted to H.264. You need to convert to YUV colour space first.
There seem to be some serious problems with banding. Any ideas?!
Encoding WMV9 from Premiere Pro 
Encoding PAL 16:9 at 1500kbps 
- Download "WM9 PAL 16-9 1500kbps 720x576.vpr" by right clicking on this link and selecting "Save link as".
- Save this file to C:\Program Files\Adobe\Premiere Pro 1.5\MediaIO\presets\system
- In Premiere Pro, go to File > Export > Adobe Media Encoder
- Select Format: Windows Media
- Select Preset: WM9 PAL 16-9 1500kbps 720x576
- Make any changes necessary (note that the datarate, audio format, pixel size and aspect ratio are set in the "Audiences" tab)
- Click OK
- Select a file name and whether or not you want to export the entire sequence and click Save
- Note that this preset is two-pass so you'll get two "Encoding" progress bars.