Как лучше реализовывать сохранение состояния пошаговой игры?
Для простоты сериализуйте Java объекты и храните их в sqlLite, который в свою очередь "вшейте" в проект. 
Плюсы :
Простота хранения
Ресурсоемкость(не требует развертования СУБД)
Скорость разработки(не требуется писать маппинг java - субд - ячейка)
Минусы :
Производительность(но для хранения состояний это не критично)
XML в наш век для таких целей выглядит как костыль. Конечно, используйте БД.
В бд можно копаться и очень просто. Есть куча софта, а если будете использовать mysql, то и разные phpmyadmin.
Подрастёте, переходите на облачные бд аля https://parse.com/ (хотя можете и сечас с ними ознакомиться).
Поддержка версий при грамотной структуре - не вопрос вовсе.
Не стоит бояться БД. Просто найдите свой подход к ним. В них не так всё сложно как кажется. Select, update, delete, insert - все команды которые вам понадобятся. Далее - вопрос структуры.
Если планируете свой сервер, начинайте учить django - там сможете почти автоматом нагенерить любую БД. Иначе смотрите в сторону облачных БД(писал выше) - как в них создать БД разберется даже домохозяин. Остальное - дело за вашим клиентом