Ваше приложение должно позвонить на ваш сервер и получить информацию.
Просто вы можете получить небольшой XML-файл с сервера и получить номер самой новой версии и сравнить его с установленной версией приложения.Если он доступен, вы можете уведомить всплывающее окно и направить пользователя на экран Android Market для обновления приложения.