Где хранятся данные, на которые указывает указатель, возвращаемый от функции, и каким образом это было достигнуто?

Переменная - это место в памяти, которое определяется адресом, а на высоком уровне - именем переменной. О взаимосвязи имён переменных и соответствующих адресов знает компилятор.

Глобально, есть всего лишь два типа переменных: значение и указатель. Переменная-значение хранит в памяти непосредственно значение, например число. Переменная-указатель хранит адрес другой переменной. Собственно, переменная-указатель - это тоже переменная-значение, значением которой является число - адрес другой переменной.

Программы делят память на несколько частей: постоянные данные (глобальные переменные, константы и пр.); динамические данные, место под которые берётся в участке памяти, который называется кучей; и стек, в котором помимо адресов возврата из функций сохраняются параметры, передаваемые в функцию, и результаты, которые она возвращает. Это всё одна и таже физическая память, но участки расположены по разным адресам. Эти адреса выдаёт приложению операционная система, когда загружает приложение в память для выполнения.

Место для динамических переменных-значений выделяется в стеке. Место для переменных-указателей тоже выделяется в стеке, а вот место под данные, на которые указывает указатель, выделяется в куче.

Поэтому:

1. "В Linux есть моного функции, возвращающих не объект, а указатель на него, хотя в реальности - это указатель на какую-нибудь стуктуру" - здесь тавтология, указатель на объект и указатель на структуру - одно и тоже в семантике этого вопроса.
2. Объект хранится в куче, указатель на него - в стеке (кроме глобальных переменных).
3. "fopen()" - это функция. Она возвращает указатель на структуру. Структура хранится в куче, а указатель на неё - в стеке. Здесь структура (struct) - это конструкция языка программирования.

Во многих ЯП структура приравнивается к значению и хранится в переменной-значении, в то время как объекты используются при помощи переменных-указателей, хотя ничего не мешает получить указатель на переменную-значение или использовать значение переменной-указателя как переменную-значение. А вот эта цепочка "переменная-указатель --> переменная-указатель --> переменная-указатель --> ..." может быть и бесконечной.

Это зависит от конкретной функции и, часто, от реализации. Есть несколько вариантов:

1. В документации указано использовать free(), например, для функции strdup(). В этом случае, да, память точно выделяется malloc()/calloc();
2. В документации указано, что никаких действий по уничтожению предпринимать не требуется, например, strerror() или нестандартный alloca(). Возвращается указатель на некоторые внутренние структуры, часто, на внутренние таблицы, а в последнем случае на область стека, такую, которая будет освобождена при выходе из вызывающей функции;
3. В документации предписан определённый порядок уничтожения. К примеру, для функции fopen() файл можно закрыть fclose() и, бывает, нестандартным fcloseall() можно закрыть все файловые потоки, кроме стандартных. В этом случае тоже, всё зависит от реализации, скажем, GLIBC выделяет malloc() память под структуру FILE, MUSL выделяет одним куском память не только под структуру, но и под буфера, а, скажем, FreeBSD имеет внутренний пул структур, т.е. выделяет память только при его расширении и достаточно долго её не освобождает. Кроме того, поскольку указанный объект может быть включён в какие-либо внутренние списки, содержать блокировки и т.п., то уничтожать его следует только документированным способом;
4. Отдельно стоит упомянуть pthread_getspecific() и tss_get() - получение указателя на элемент локальной память потока, которая выделяется и освобождается, но хитро, часто, при запуске и завершении потока.

В общем, выделить и пересказать все варианты, например, mmap() совершенно невозможно. Так что стоит в каждом случае читать, как минимум, документацию и стандарты.