Hello.
I have always done the promotion inside the Execute method like this:
IBaseMessageContext myContect = inmsg.Context;
myContect.Promote(this.ProElementName, this.ProNameSpace, this.ProValue);
This will put the value into the context. You can need to get at the value inside the Orchestration like this:
yourMessage(PropertyName);
Also, make sure you have a Property Schema deployed with the correct namespace and element name.
I have a sample that shows this in a little more detail include with the Limit Running Orchestration sample: http://www.biztalkgurus.com/Samples/Limit-Running-Orchestration.html
Hope this helps.