Isso é o que eu faria:
Verificando a versão mais recente em seu servidor, em um arquivo de texto:
HttpClient client = new DefaultHttpClient();
HttpGet request = new HttpGet(url);
HttpResponse response = client.execute(request);
String latestVersion = "";
InputStream in = response.getEntity().getContent();
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
StringBuilder str = new StringBuilder();
String line = null;
while((line = reader.readLine()) != null)
{
str.append(line);
}
in.close();
latestVersion = str.toString();
e depois compare com a versão instalada:
private String getSoftwareVersion() {
try {
PackageInfo packageInfo = getPackageManager().getPackageInfo(getPackageName(), 0);
return packageInfo.versionName;//EDIT: versionCode would be better
} catch (PackageManager.NameNotFoundException e) {
Log.e(TAG, "Package name not found", e);
};
}