The portion of the plugin that is PowerShell is probably the piece that goes onto the VSTS server, which is Windows only AFAIK. The plugin that you install in Artifactory should be Java/Groovy, because that is what Artifactory itself is programmed in. If you have a Linux VSTS build agent you can still use the Artifactory CLI to perform deploys/promotions or use the REST API. I'm not positive but fairly certain that even if you are using all Linux agents, the VSTS coordinator/master server that is hosted by VSTS runs Windows, and that is where the artifacts will get copied back to and promoted from.
It does appear that the task is actually running on the build agent.
Here is the error:
2016-07-29T01:36:52.8159870Z ##[section]Starting: JFrogArtifactoryPromote
2016-07-29T01:36:53.0988410Z ##[error]Supported task execution handler not found. Supported handlers: Node
2016-07-29T01:36:53.1038520Z ##[section]Finishing: JFrogArtifactoryPromote
As you see the only handler supported is Node, not PowerShell (my agent runs on Linux)
When I unzipped the JFrog.jfrog-artifactory-1.0.0.vsix extension and looked at the JFrogArtifactoryPromote's task.json, I saw the following: