Various zones will have groups of 'shadowy' monsters. The monsters initially appear as NPCs, but will become aggro and attack when players get close. They scale to one level below the player's level v, and attack in a group of three.
On defeating them, they will drop a treasure chest with a strangely marked hide inside. Examine it to start the quest.
These creatures are not visible on Time Locked Servers until after Destiny of Velious is activated there. 
Types of shadowy beasts and their locations below.