Прочитайте man dpkg и man apt-get. Ваша первая команда должна была быть sudo apt-get remove gitlab-ce, затем sudo apt-get purge gitlab-ce. Команда autoremove просто удаляет пакеты, которые были установлены из-за требований другого пакета, но другой пакет был удален.