A shadow assassin is a form of magic Lady Melisandre of Asshai has used to murder Lord Renly Baratheon  and Ser Cortnay Penrose during the Siege of Storm's End.  Once a shadow assassin is released it appears that the death of the person it is meant for is inevitable, unless there is also a way of counterattacking that may perhaps be known to magic users who are familiar with shadow assassins.
The only person that we have seen to conjure a shadow assassin thus far is Melisandre. Since a shadow is a "servant of the light", Melisandre is able to invoke the human-like shadow assassin and direct it against her enemy.
Later, the shadow assassin becomes more shadow-like and difficult to detect by eye. The shadow assassin is armed with a sword, similar to the flaming sword wielded by Stannis. When the shadow assassin attacks its target it is nearly invisible. It uses it’s sword and stabs for the neck before disappearing.
The effect on Stannis Baratheon is significant. He appears to have aged years after siring a shadow assassin on Melisandre. Davos notices that his eyes are like dark blue bruises in the hollows of his face. Perhaps this is why no shadow assassin is used during the Battle of the Blackwater. Stannis perceives the actions of the shadow assassins as their own through dreams. 
A Clash of Kings
Melisandre conjures and births a shadow assassin which she uses to murder Renly Baratheon after he refuses to bend the knee to his older brother.  Both Catelyn Stark and Brienne of Tarth witness Renly’s death. Catelyn Stark saw a shadow that looks like Stannis and a shadow sword swung, cutting King Renly’s throat, the shadow then disappears. 
After Renly's assassination Storm's End was besieged by Stannis and his army. Ser Cortnay Penrose, who was left charge of the castle, refused to yield Storm's End and Edric Storm, Melisandre had Davos Seaworth sail her under the stronghold. Melisandre disrobed, and Davos watched in horror as the now pregnant woman gave birth to another shadow assassin. As the shsdow emerged Davos recognised the man who had cast it. The shadow goes to slay Penrose. 
A Storm of Swords
Melisandre visits Davos in his prison in Dragonstone. She tells him that shadows only live when given birth by light. She admits to him that Stannis’s fires now burn so low that she dare not draw off any more to make another son, as it might well kill him. She than implies that she can make more shadow assassins with another man, a man whose flames still burn hot and high… and then adds that if Davos truly wishes to serve his king’s cause to come to her chamber one night. She tells him that she could give him pleasure such as he has never known, and with his life-fire she could make… Davos then interrupts her by saying,
A horror. 
Later, upon her arrival in King's Landing, Brienne of Tarth is confronted by Ser Loras Tyrell over Renly’s death. She tries to explain to him that there was a shadow and that she knows how mad it sounds, but,
When meeting with Jaime Lannister Loras admits to him that Renlys steel gorget was cut through with one clean stroke. He tells Jaime that Renly had the best armor, made of the finest steel and that even the Mountain would have needed a heavy axe. 
A Feast for Crows
Brienne is haunted by Renly’s death. During her quest she dreams of what happened in Renly’s tent,
All the candles were guttering out and the cold was thick around her. Something was moving through green darkness, something foul and horrible was hurtling toward her king. She wanted to protect him, but her limbs felt stiff and frozen, and it took more strength than she had just to lift her hand. And when the shadow sword sliced through the green steel gorget and the blood began to flow, she saw that the dying king was not Renly after all but Jaime Lannister, and she had failed him.