Google started with paying other software companies to bundle Google Toolbar in with their software, which would change your default search to Google. (This behavior was later changed to Google Chrome, which you still get with a dozen other programs today.) This is actually a big part of Sundar Pichai's claim to fame at Google, and likely chiefly why he is CEO today: He's responsible for Google being the default place for search.
As noted in this article, Google has been paying to be default on the iPhone for years, and Google used to be the highest bidder for Firefox's default search spot as well (and still is in several other countries besides the US).
People use the default, and Google invested an incredible amount of money in ensuring they were the default everywhere. Google has been the default in both Chrome and Firefox for many years, and used the Toolbar to change people's default in IE, and has also been the default on both iOS and Android mobile phones. And that is why Google has the market share it does today.