The new Edge is great but since it’s from Microsoft, Bing is the default search engine out of the box. To change it, you can simply go to the Settings page, Privacy, search, and services, and click the Address bar and search at the bottom of the page. From there, you can manage search engines, add or set one as default, etc.
This will be fine if you are setting it for yourself. If you have many computers to manage through Active Directory, setting it up via Group Policy make things a lot easier.
Open Group Policy Manager, heading over to the following:
User Configuration > Policies > Administrative Templates > Microsoft Edge
Double click the Manage Search Engines setting on the right.
And type the following in the box:
Click OK to save the setting.
Microsoft Edge has a beautiful new tab page that has a search box defaulting to Bing. So to make things a bit more consistently, I’d recommend to enable and set the “Configure the new tab page search box experience” policy to Address bar. What it does is that when you type the search term in the search box in the new tab page, it will redirect you to the address bar, which uses the browser’s default search engine.
The policy is located at:
User Configuration > Policies > Administrative Templates > Microsoft Edge > Default search provider
I believe that should be it.