Nomad

Вопрос решен. Требовалось дописать раздел "before_script":

before_script:
  - sudo apt update # для Ubuntu/Debian
  - sudo apt install -y maven

По крайней мере это решило мою проблему

UPD: если я верно понял, то это должно работать, исходя из утверждения

Каждая job в GitLab CI запускается в новой, независимой среде, обычно в новой директории.

Ключевой фразой тут является словосочетание "независимая среда", так как для этой независимой среды мы и устанавливаем Maven. Если я все верно понял, то для gitlab runner нет разницы установлен maven в систему или нет (не могу сказать того же про Docker - не пробовал). Он требует чтобы пакет Maven был установлен в его независимой среде! Решение, конечно, не самое очевидное, но... Что делать. Другого варианта с моим уровнем знаний (оно чуть выше дна) я пока не придумал.