Generally, Internet Explorer 11/10/9 comes with Bing as default search engine (both are made by Microsoft). The search comes from typing keywords in the address bar, or right-clicking on selected text and searching for it. Since IE9, the address bar and the search box have merged into a single text box. (In IE8 and IE7, there was a separate search box on the right of the address bar).
The "search provider" is the search engine that powers web searches you perform from IE. Changing the default search provider just means changing the search engine to which searches are passed by default. Click on the Tools menu (gear icon in the top right corner), and choose "Manage add-ons". When the dialog opens, select "Search Providers" on the left.
If the search engine you want to use isn't listed, you'll need to install it as a search provider: click on the Find more search providers link in the bottom left corner. Select a search engine in the listing, and click on the "Add to Internet Explorer" button. When the popup opens to add the new search, you can check the "Make this my default search provider" checkbox.
If you added a new search engine in the previous step, start over with the Tools menu to go back to the Manage Add-ons dialog. Click on the search engine you want to use as default. Click on the "Set as default" button, and make sure that "Search in the address bar and the search box on the new tab page" is selected: depending on your new tab settings, a search box will appear whenever you open a new blank tab (the special "about:tabs" page).
Searches you type in the address bar will automatically be handled by IE's default search engine. To search the internet with a different search engine, you can select text on a web page, right-click on it, and choose a search engine from the context menu: your current default is in the menu itself, and your other search providers are under the "All Accelerators" submenu. When right-clicking, hit the letter "S" for a default search (it's an access key!)