A Soul Shard is created when a Warlock kills an enemy that is under the effect of :Drain Soul. It is automatically soulbound to the Warlock. Note that the enemy must reward either experience or honor; that is to say, their level must be green or higher in the unit frame. Also note that Drain Soul does not have to land the killing blow in order to create a Soul Shard.
Contrary to the name of the ability, Drain Soul does not have to be used on enemies that you would expect to have a soul. Even demons will reward a Soul Shard if killed while under this effect. (Yes, that includes the Blood Elf who ganked you five times. Even if he is a soulless weasel, you still get a Soul Shard.)
Every Warlock summon after the very first (the Imp) requires a Soul Shard to cast. There are various other spells using Soul Shards, as well:
One common method of regaining Soul Shards is to tell a pet to Stay, then run away from it until it is automatically dismissed. If a Soul Shard was used to summon it, then it will be reimbursed.
With all the different abilities that make use of Soul Shards, some Warlocks find it beneficial to carry special bags to assist in holding a large number of them.