To do this, you have to create a Feature which references a WorkflowActions element file. You can find a typical walkthrough at http://msdn.microsoft.com/en-us/library/ff798499.aspx
The problem is that a Feature is targeted at a specfied scope and in the context of a Sandboxed deployment, the two possible scopes available are Site (you target all sites in a given Site Collection) and Web ( you target a specific Web Site inside the Site Collection).
When you google around, the scope is fixed at Site with no explanation. Even on MSDN and in the SDK you are told to set the scope at Site!
As usual, any source of information found on the web should be partially trusted !
This post is the result of another journey in the SharePoint Galaxy.
So where is the information that could be trusted about the possible WorkflowActions scope ?
Of course in the SharePoint API.
So I asked Sir Reflector to assist me in this journey. As usual Sir Reflector always gives an anwser.
Inside the SharePoint API, you have a method called Validate on a SPElementDefinition class:
1: if ((((type == typeof(SPContentTypeBindingElement)) || (type == typeof(SPEventElement))) || ((type == typeof(SPListInstanceElement)) || (type == typeof(SPListTemplateElement)))) || (((type == typeof(SPModuleElement)) || (type == typeof(SPFieldElement))) || (((type == typeof(SPPropertyBagElement)) || (type == typeof(SPWorkflowActionsElement))) || (type == typeof(SPContentTypeElement)))))
3: flag = (scope == SPFeatureScope.Web) || (scope == SPFeatureScope.Site);
The above code (from the SharePoint API) is very clear : a Workflow Action can be deployed at two possible levels : Site or Web.
End of the story.