Tokenы

https://tools.ietf.org/html/rfc7519

и в базе хранить не обязательно

Как хранят сгенерированный токен?

Как хранить это уже второй вопрос. Можете хоть в БД, хоть в Memcached/Redis/etc. Это не так важно. Важно обеспечить безопасность.
Как минимум HTTPS, дабы избежать элементарного mitm.

этот токен принадлежит и столбец expire_date (нужен ли он вообще)

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

Когда пользователь зарегался впервые и сервер вернул сгенеренный токен, где его необходимо хранить? в кукисах?

Нет, конечно же, RESTful и cookie - понятие несовместимые. Во-первых, зачем вы собрались генерировать и отдавать токен после регистрации? Токен вы будете отдавать при аутентификация на запрос пользователя. Придерживайтесь нескольких простых правил при отправке токена:

• не используйте HTTP basic auth, если не уверены что абонент, запрашивающий токен сможет безопасно его хранить.
• во всех остальных случаях, используйте oauth2 bearer tokens, либо с помощью параметризации в URL, тут уже как вам удобно будет.

Ну и самые элементарные вещи - никаких сессий, верные коды состояний (например, 401 Unauthorized при ошибки аутентификация) и т.д. и т.п.
И вот только после того как все условия выполнены, и клиент был успешно аутентифицирован, можете смело приступать к авторизации :)

Хотелось бы еще спросить про то, как организовать правильнее urlы, можно ли через GET /users отдавать форму регистрации пользователя

На последний вопрос вообще не смогу вам ответить. Какая форма регистрации через RESTful?

Или это можно добавить в таблицу users?

У юзера может быть несколько одновременно выданных токенов, если сервис не запрещает использование с нескольких устройств одновременно. Делать это в некоей таблице users было бы достаточно неудобно.