Как мне этого добиться?
У вас нет возможности обнаружить переустановку. К счастью, этого не происходит, кроме как во время разработки, AFAIK.
Чтобы обнаружить обновление версии, сохраните копию своего versionCode в предпочтении. Сравните его с работающей копией, когда ваш код запускается. Если ваше приложение новее, чем versionCode в настройках, оно обновлено, и вы можете делать все, что считаете нужным.
Обратите внимание, что это довольно необычное поведение, и пользователи могут дать вам плохие оценки на Маркете, если они чувствуют, что теряют информацию из-за обновления.