Github and Gitlab are both companies that do more or less the same thing; they provide a hosted Git service.
The main difference is that Gitlab is open source and you can download and run the community edition on any machine you want for free. This is why Gitlab's popularity has skyrocketed over the last few years.
Github, while they do offer on-premises services (at a cost), make most of their money through their centralised online offering, github.com. Nearly all open source projects use it (or at least have a presence there) because when they started it made the process of forking and submitting code (in the form of pull requests) simpler than it had been in the past.
Additionally, Gitlab has plenty of extra features that Github doesn't, such as continuous integration, a docker registry.
Github, instead, offers more in the way of integrations with other SAAS providers via the Github marketplace.
Which should I choose?
I want to install and run on my own server with as many users as I like. Gitlab
I want private repositories but I don't want to run anything on my own server, I'd rather have it managed by a company with a good record of performance and uptime : Bitbucket or Gitlab for free. Or, one of Github's paid plans
I want to write open source software and have plenty of visibility online. Github