From Apple Computer
"Motorola's AltiVec Technology, embodied in the G4 processor, expands the current PowerPC architecture through addition of a 128-bit vector execution unit, which operates concurrently with existing integer and floating-point units. This provides for highly parallel operations, allowing for simultaneous execution of up to 16 operations in a single clock cycle. This new approach expands the processor's capabilities to concurrently address high-bandwidth data processing (such as streaming video) and the algorithmic intensive computations which today are handled off-chip by other devices, such as graphics, audio, and modem functions.The AltiVec instruction set allows operation on multiple bits within the 128-bit wide registers. This combination of new instructions, operation in parallel on multiple bits, and wider registers, provide speed enhancements of up to 30x on operations that are common in media processing."
In plain english, this means the "Velocity Engine" (as it is otherwise known), allows the CPU to do multiple mathematical operations with one machine instruction. This is accomplished by trading precision (in the form of word length) for parallelism, by packing multiple smaller precision numbers into a single 128-bit word (2 64-bit numbers, 4 32-bit, etc.) and doing a "batch" operation on them all at once - addition, multiplication, whatever.
It's Motorola's answer to MMX, SSE/SSE2, 3DNow!, or whatever Intel and AMD are calling it these days - and in fact, can be generally characterized as a SIMD (Single Instruction Multiple Data) extension to the PowerPC ISA - and a common evolutionary development path of the personal computer CPU.