Set up a server that exposes an HTTP url that reports the latest version, then use an AlarmManager to call that URL and see if the version on the device is the same as the latest version. If it isn't pop up a message or notification and send them to the market to upgrade.
There are some code examples: How to allow users to check for the latest app version from inside the app?