One major inhibitor on execution via the game mechanics is that spirit walking can allow a character to recover from a death only slightly worse for wear. I can agree though that it should be a top tier punishment for top tier criminals, and so when issued should involve holding the criminal in prison long enough that their fame and age will make it so that its almost impossible to make it back from their spirit walk. If the legal system employs a spirit walker they can possibly assist in ensuring effective execution by preventing a person from completing their spirit walk as well (I don't think this was their original intention behind the talent but I am sure it will be used this way in some cases.) Ultimately more infamous criminals will be more likely to be executed because they are much more likely to actually face permadeath. And that's how it should be, execution should not be a tossed around sentence for any crime.
As for methods of execution, I would say things like hanging, drowning, or other methods would be ideal, namely things a person could theoretically survive. This is because there is always a chance that the person will complete their spirit walk despite any circumstances and come back to life. In those cases it can be said they survived execution by a miracle, and they can continue playing with their much shortened life span. If you simulated cutting their head off there really is no explaining how they would have survived.