Gmail succeeded back then because everyone was switching to it for the free storage space and to be the cool person with a new gmail address. This happened long enough for new internet users to start choosing gmail for their first email, eventually becoming the majority email provider.
That doesn’t explain how Gmail became ubiquitous. Back when it started, Hotmail, Yahoo Mail, AOL were very popular (among many others). Since it was not yet ubiquitous, Gmail’s ubiquity could not be an explanation for success.