As far as I understand, the main difference is that gitlab-ci is opensource (you can install it on your own server) and travis-ci isn't.
So then the latter is always cloud/service-based. And it's free for open source projects.
But then GitLab.com (the company, not the software) also has a cloud version that you don't need to install: ci.gitlab.com. And I'm guessing this version can only be used with public repositories posted in your Gitlab account.
But then, there's almost no documentation out there about running GitLab CI this way. Most of the docs I find are about installing the GitLab CI server or the runners. But how are the ci.gitlab.com's runners configured? What OS do they have? Can I have Windows/Mac runners? (The software supports these OSs apparently, but it's not specified what runners are supplied by ci.gitlab.com's service.)
Edit: 29/06/2016
As comments suggest, now gitlab is offering what they call shared runners. This means that you no longer need to bring your own runner, you can use theirs instead and use it just like travis CI, but there is a limit of 2,000 minutes of CI run-time per month for the free tier.
** Previous historic answer **
Gitlab CI can be used online, but you must bring your own runners. What does this means? You need to install a piece of software in your servers which will run the tests. Its more complex than travis.
After installing you have to associate it with your project, and configure it if you want to run tests inside docker or in your bare hardware. There are few more options.
Each time you push a commit to gitlab, a hook is triggered to gitlab ci and a build is sent to an available runner which executes the build and tests and send back tests results to gitlab ci server.
Now, with the last update, gitlab ci is inside gitlab, but it is still the same.