I've killed a few people with a cinematic execution kill, but I have no idea how. Is it something like when their stamina is all the way down you can execute them?

I'd like to know this as well. Is it entirely random, or is there a way to force them? I accidentally pressed the sprint button while fighting and then I did an execution kill, but I'm not entirely sure.

its random

the heavy attack

It's random, plus IIRC there's some perk for an additional chance to decap/kill.