How to release application plugin using Android Market?

It's quite simple in your case, since you don't need any extra logic, but just more levels, so I will stick to this specific case:

You can (or probably already do) have your game levels saved as resources in your .apk, so a plug in can be a standard .apk, that will not appear in the list of users-apps. To prevent it from appearing, simply don't declare the category-launcher:

<intent-filter>
   <action android:name="android.intent.action.MAIN" />
   <category android:name="android.intent.category.LAUNCHER" />
</intent-filter>

Once the snippet above does NOT appear in your plugin's AndroidManifest, it will not be directly accessible to the user.

When your main game activity starts, it should check for the existence of plugins, you can do it, by calling PackageManager.queryIntentActivities. And querying for a specific intent you declared in the AndroidManifest file of your plugin, for example:

<intent-filter>
  <action android:name="com.your.package.name.LEVEL_PACK" />
</intent-filter>

The query code would then be:

PackageManager packageManager = getPackageManager();
Intent levelsIntent = new Intent("com.your.package.name.LEVEL_PACK");
List<ResolveInfo> levelPacks = packageManager.queryIntentActivities(levelsIntent, 0);

There are more ways to do this, but this is quite trivial and straight forward.

The last step is to access the levels from the installed level-packs. You can do this by calling: PackageManager.getResourcesForActivity and load the relevant resources and use them as you will.