I've tried escaping the hyphen, which returns invalid search query. I've tried surrounding the environment name with double quotes. The search works fine for environments without a hyphen, such as "staging".
$ knife search node 'environment:staging'
22 items found
…
I'm using knife from Chef 11.8.2 and the Chef server is 11.0.10.