Как операционная система понимает, сколько нужно очистить память?

Выделяется не 256 байт, а служебная структура + 256 байт (а при страничной адресации так и вообще выделяется минимум 1 страница). Вот в этой служебной структуре и хранится перед выделенным блоком информация о самом блоке.

Как операционная система понимает, сколько нужно очистить память?
Ни как. Ей фиолетово. А вот ваша прога это другое дело.
char *array = malloc(256);
теперь компилятор знает, что переменная array 256 байт
free(array); //!
и тут компилятор подставит в код очистки адрес переменной и ее размер.

А free() вовсе не означает, что ОС освободит память.
Напротив - скорее всего память останется у вашей программы.

https://learnc.info/c/memory_allocation.html

ну, примерно так же, как она понимает, что память уже занята (аллоцирована).
таблица есть, вероятно.

Факт 1. malloc и free реализуется не ОС, а рантайм-библиотекой языка C/C++. Да, безусловно, время от времени рантайм библиотека делает системные вызовы для того чтобы получить от ОС адресное пространство, но делается это далеко не на каждый malloc/free.

Факт 2. Вам нужно чётко понимать, что работаете вы со средствами языка и стандартной библиотеки языка, а не ОС. Если на каком-то устройстве скомпилированная программа на C должна работать без ОС, то и способы реализации функционала malloc/free будут иные.

Факт 3. Алгоритмы, реализующие работу malloc и free, хранят довольно много служебной информации для себя, в частности размер и положение выделенных блоков. Вы не имеете непосредственного доступа к этой информации, но это не значит что её нет. Её достаточно как минимум для того, чтобы выделять вам новые блоки и корректно освобождать старые. Такие алгоритмы называются менеджерами памяти. Кстати в этой незамысловатой статье на вики написано о так называемой иерархии менеджеров памяти. Если вы ознакомитесь с этим понятием, узнаете наверняка больше, чем из всех ответов вместе взятых.