Таким образом, ответ на этот вопрос был в других ответах, но они также содержали вводящий в заблуждение код (в любом случае, на моей машине: Win7x64).
Вот что сработало, а что нет (опять же для меня).
Этот код ничего не сделал с заголовком:
tableView->horizontalHeader()->setStyleSheet("background-color: black;");
Этот код работал, но также изменил границу всего виджета QTableView:
tableView->setStyleSheet("QHeaderView::section {
background-color: red;
color: white;
border: 1px solid #6c6c6c;
}");
Этот код работал как ожидалось:
tableView->horizontalHeader()->setStyleSheet("QHeaderView::section { background-color: rgb(40, 0, 0) }");
Этот код также работает, вариант на приведенном выше:
tableView->horizontalHeader()->setStyleSheet("::section { background-color: rgb(40, 0, 0) }");