Можно ли возвращать лямбды?

Вот так делать - это нормально?

Вполне

И что в таком случае возвращается, указатель на функцию или сама функция?

Функциональный объект. Лямбда — не функция, она может быть приведена к указателю на функцию в некоторых случаях.

Если возвращается указатель, то где хранится сама функция, в куче или стеке?

«Функция» лямбды хранится там же, где и остальной код. На лету ничего не собирается и не компилируется. Лямбда это синтаксический сахар для объявления класса с перегруженым оператором вызова функции.

И еще один вопрос, по этой же теме:
Это сокращенная запись вот такой конструкции:
Или что то другое?

lambda имеет уникальный тип. Это не функция (но может быть приведена к ней в данном случае).

Добавлю пару примеров к сказанному MiiNiPaa:
Вот такой код:

auto GetLambda() {
    return []( const int &x ) { return x*x ; } ;
}

это синтаксический сахар для такого (все это можно было писать еще и до появления лямбд):

struct Lambda {
	int operator()(const int &x) { return x * x; }
};
Lambda GetLambda() {
	return Lambda();
}

Отличие в том, что явно класс не создается, но принцип тот же. Возможно, на этом примере вам непонятно, зачем вся эта заморочка с классом. Поэтому рассмотрим другой пример. Этот код

auto GetLambda(int y) {
	return [y](const int &x) { return x*y; };
}

можно переписать так:

struct Lambda {
	int y;
	Lambda(int y) : y(y) { }
	int operator()(const int &x) { return x*y; }
};
Lambda GetLambda(int y) {
	return Lambda(y);
}

Как видите, захват значения локальной переменной и "сопровождение" им кода лямбды осуществляется с помощью оборачивания в класс. Если еще не знакомились с замыканиями, самое время это сделать.