Variable Bitrate
In Variable Bitrate (VBR) coding, the user chooses the desired quality level and/or a range of allowable bitrates. Then the encoder tries to maintain the selected quality during the whole stream by choosing the optimal amount of data to represent each frame of audio. The main advantage is that the user is able to specify the quality level and conserve as much space as possible, but the inconvenience is that the final file size is quite unpredictable.
Most modern encoders are able to perform VBR encoding, including (but not limited to) nearly all popular MP3, AAC, (Ogg) Vorbis, Musepack, and WMA encoders.
Some codecs limited to Constant Bitrate (CBR) include AC3 (in theory it can encode to VBR, but no high quality encoder offers that feature), DTS (same thing as AC3, no publicly available VBR encoder), Real Audio and ATRAC3.
Most lossless codecs are VBR.
To help players seek and show correct durations, VBR formats often include metadata at the beginning of the file to indicate the total duration and provide a "seek table" of the offsets, within the file, of a set number of points, each a fixed duration apart. For example, the seek table may have 100 offsets to represent 1%, 2%, 3%, etc. of the way toward the total duration. This feature is sometimes also used in CBR formats, so that tags don't confound file-size based estimates of duration and seek points.