Да, два приложения могут общаться через Интернет (или через Bluetooth или смс / ммс, но менее практично). Так же, как любые два компьютера могут общаться через Интернет. Существует большое разнообразие протоколов. Весь мир на самом деле. Вам нужны ссылки на некоторые учебные пособия по работе в сети или я полностью пропускаю ваш вопрос?
РЕДАКТИРОВАТЬ: Вы можете попробовать Руководство по TCP / IP для вступления
РЕДАКТИРОВАТЬ: И для Android вы, вероятно, хотите использовать их интерфейс сокета
ОБНОВЛЕНИЕ: О том, как общаться между клиентами - вы, вероятно, не хотите полагаться на знание IP-адреса конкретного партнера. Обычно вы работаете с каким-то известным хостом в качестве сервера, который координирует между одноранговыми узлами, иногда передает сообщения между ними или, альтернативно, просто уведомляет клиентов об адресах друг друга.