Ролг Хупин, нужно смотреть в сторону oAuth.
А по сути реализация примерно такова:
1) Клиент вызывает сервис Authentication c логином, паролем, имя сервера и т.д. все что необходимо.
2) Сервис создает уникальный сессионный токен (билетик), пишет все имя сервера и т.д. что необходимо в сессионную таблицу напротив токена. Токен возвращается в ответе клиенту.
3) Каждый следующий вызов клиент поставляет этот токен вызываемому сервису. Сервис проверяет сессию на валидность, вытаскивает по нему данные и далее уже выполняет нужную операцию.

2 момента:
1) Сессии нужно проверять на сервере и чистить по истечении какого времени, т.е. сессия не должна оставаться навечно.
2) Использовать SSL для безопасности данных медлу клиентом и сервисом.

Ролг Хупин, и, да - WCF тут не пр чем. Все RESTful

Ролг Хупин, этим общедоступным местом и будет таблица сессий в БД. Соответственно апликейшн серверам под лоадбалансером будет все равно какой из них обрабатывает запрос клиента.

Ролг ХупинЕсли сессии храниить в Redis, то им можно сразу назначать время жизни и не заморачиваться.
Надо учесть, что сессия не должна тупо истечь по истечении N количества минут, а необходимо продлять на N минут после каждого запроса клиента.

Ролг ХупинКак клиент должен передавать токен, чтобы было все по идеологии RESTFul?
В header'е запроса.

Ролг Хупинт.е. лучше хранить сессии в каком-то общедоступном Storage, чем гонять строку во все методы с зашифрованными данными?
Как Вы себе это представляете? В случае с Web Application, Ваша сессионная аутентификационная кука автоматически гоняется в запросе к вэб серверу. В случае с сервисами Вы создаете запрос к сервису программно.

Ролг ХупинAxeleronпропущено...

Как Вы себе это представляете? В случае с Web Application, Ваша сессионная аутентификационная кука автоматически гоняется в запросе к вэб серверу. В случае с сервисами Вы создаете запрос к сервису программно.

имеется в виду, что эта кука не некий ключ к таблице сессий на сервере, а строка содержащая в зашифрованном виде все данные для логина
И зачем лишнюю информацию каждый раз гонять с клиента в сервис?