When I was first starting to look, I thought it would be done in the same way an Air Application is updated (see here and here for more info on updating air projects). Updating Flex Mobile Apps doesn’t work this way. Quote:
The AIR update framework is only supported in the desktop profile. It is not supported for extended desktop applications (applications installed with a native installer), and it is not supported on the mobile profile (iPhone applications written with ActionScript 3.0). Check the Updater.isSupported property at runtime to see if the update framework is supported.
If you would trace out Updater.isSupported in your Flex Mobile Project, is would return false.

Android

For apps distributed on the Android Market, you can update an app by placing a new version on the Market, as long as the following are all true (these policies are enforced by the Market, not by AIR):

• The APK package is signed by the same certificate.
• The AIR ID is the same.
• The versionNumber value in the application descriptor is larger. (You should also increment the versionLabel value, if used.)

Users who have downloaded your app from the Android Market are notified by their device software that an update is available.

Note that to submit an app to the Android market, the certificate validity must be 25 years or greater. That pretty much rules out using commercially issued certificates, so the renewal issue is moot. At least for now. At some point I think Google will have to change their policy here since the level of cryptology involved isn’t really suitable for such a long validity period.

iOs

For AIR apps distributed through the iTunes app store, you can update an app by submitting the update to the store as long as the following are all true (these policies are enforced by the Apple app store, not by AIR):

• The code signing certificate and provisioning profiles are issued to the same Apple ID
• The IPA package uses the same Apple Bundle ID
• The update does not decrease the pool of supported devices (in other words, if your original application supports devices running iOS 3, then you cannot create an update that drops support for iOS 3).

Important: Because the AIR SDK versions 2.6 and later do not support iOS 3, and AIR 2 does, you cannot update published iOS applications that were developed using AIR 2 with an update developed using AIR 2.6+.

So, for Android, you need to have good versionNumbers. iOs seems to deal with it himself, every time a new version is online, it will be updated (versionNumber will be ignored).

Usefull links:

Updating mobile AIR applications

Android Market & Developer signup

IOS Developer Program

IOS Developer Member Center