Two of the pins on the l293d are labeled VS and VSS. Apparently they are both power. Here it shows VS being supplied with 12V, while vss is receiving 5V. Here, it shows both receiving 6V from the same source of 4AAs. What are each of these for? Also, in the second link, he shows wiring to the ground on the arduino, why is that? Wouldn't he be able to do the same by wiring to the negative terminals on the batteries?
One is logic power (pin 16 (20 for SMD) at top right,should be 5v or whatever your logic level is), the other is motor power (pin 8 (10 for SMD), bottom left, can be from 4-36v and should be whatever your motor needs).
This means you can run your motors at different voltage, and also isolates power spikes from the motor supply from the logic.
Have a look at the bipolar stepper motor example circuit here: http://www.tigoe.net/pcomp/code/circuits/motors/stepper-motors (The circuit says SN754410NE, that device is just a higher power version of the L293).