ВКонтакте API

Смотрю на приложения, и там можно сохранять разные данные у себя в приложении. Так вот, это работает на стороне сервера:
Пользователь авторизируется через ВК и через базу данных берутся его данные и все дела, или же как-то на стороне API ВК?

все нормальные приложения хранят данные у себя в БД.

Когда пользователь запускает приложение, твоему скрипту отправляется большой список GET-параметров. Список здесь http://vk.com/dev/apps_init. Там среди всего прочего и viewer_id - id пользователя. Вот имея этот id можешь творить с пользователем что хочешь. Какие данные хранить у себя на сервере каждый выбирает исходя из задач.