Сетевая игра на Android, как писать?

У вас должен быть клиент, сервер и протокол взаимодействия клиента с сервером.
В простейшей части клиент соединяется с сервером, авторизуется и тут уже вступает игровая-бизнес логика.
Сервер принимает соединение, авторизует игрока (идентифицирует его) и тут опять же вступает игровая-бизнес логика на сервере.
Протокол однозначно должен идентифицировать все действия клиента и все ответы сервера.
Т.о. последовательно общаясь сервер и клиент реализуют игровую ситуацию.

Внутри сервера логика должна быть гораздо сложнее клиентской, т.к. сервер реализует не только правила самой игры, но и всяческие проверки на "дурака", чтобы клиент не мог читерить. Также сервер должен организовать взаимодействие между игроками. В простейшем случае это некая игровая комната, а внутри неё 2 и более игроков создают игровую ситуацию по правилам игры.

Если хотите писать сервер с нуля, то рекомендую посмотреть в сторону Erlang.
Там за каждого клиента может отвечать свой процесс, за игровую комнату тоже. И т.о. вся реализация игры сводится к правильной посылке сообщений от процесса-игрока, к процессу-комнате и обратно с реализацией игровой логики внутри процесса-комнаты.

В целом вот так. Если будет нужна помощью в Erlang, или написании такого сервера могу помочь. В том числе и ответами на данном ресурсе.

Первое, с чем надо определиться - это что Вы подразумеваете под сетевой игрой: игра через Интернет (через выделенный сервер) (актуально если Вы хотите координировать игры и содержать, скажем, общее для всех игроков игровое пространство или, хотябы, общий рэйтинг и список игроков), игра через локальную сеть (не слишком актуально в случае Android-устройств, наверно), игра через BlueTooth (удобно для игры в поезде, например).

Потом изучать работу с соответствующими технологиями: в первом случае это будет HTTP/HTTPS или TCP/UDP, во втором тоже (хотя скорее вторая пара), в третьем - собственно BlueTooth-стэк.

HTTP/HTTPS-клиенты программируются через стандартные библиотеки элементарно, TCP/UDP - чуточку сложнее, про BlueTooth ничего не могу сказать.

По части "частей" - мне кажется это было бы очевидно если бы Вы имели малейший опыт написания приложений для Android вообще и реализации паттерна MVC в частности, так что сначала потренеруйтесь немножко, напишите что-нибуть простенькое не сетевое для начада (сначада "Hello World", потом хотябы банальные крестики-нолики какие-нибудь), а потом пробуйте прикручивать к тем же крестикам-ноликам сеть, задавайте конкретные вопросы по мере возникновения, и двигайтесь дальше.

Если я прав и Вы действительно ничего ещё не писали - рекомендую поставить IntelliJ Idea Community Edition и начать с тамошнего quick start-а.