After lots of digging, I've found a solution, but it's made me realize that this post probably should have been three separate questions.

RE: How to use Java Plugins in Unity
The documentation for Unity includes a page describing plugins. Under the Android section, there is a description of how to make a jar file and use AndroidJavaObject to access it in Unity.

RE: How to make and save an Android Screenshot
First, according to this post, androids have problems encoding to PNG. This post provided a link to an alternative jpg encoding.

Second, to view the screenshot from the android file manager, the file path needs to be set using Application.persistentDataPath . More in this post.

RE: Android Gallery
[EDIT] Still working on this... After taking a screenshot, the image does not show up in the gallery regardless of the filepath. However, on rebooting the phone, it does a media scan and automatically adds all image files to the gallery, again regardless of the filepath. There is a post about forcing a media scan, but I have yet to try out the answer

This plugin looks like it will do the trick:

https://www.assetstore.unity3d.com/#/content/7827

I got a partial answer for the 'saving an image in the users gallery on Android' part of the question. That's how we do it in native Android. I will look for a solution from Unity.

final Bitmap bitmap = INSERTSOMEVIEWHERE.getDrawingCache();
final File appSzenesFolder;
try {
    appSzenesFolder = directoryAndStorage.getOrCreatePictureDirectory("NameOfTheImageFolderInTheGallery");
    final Date now = new Date();
    final File file = new File(appSzenesFolder, (now.getTime() / 1000) + ".png");
    file.createNewFile();

    final FileOutputStream ostream = new FileOutputStream(file);
    bitmap.compress(CompressFormat.PNG, 100, ostream);
    ostream.close();

    // Tell the media scanner about the new file so that it is immediately available to the user.
    MediaScannerConnection.scanFile(this, new String[] { file.toString() }, null, null);
} catch (IOException e) {
    // Insert error handling here :)
}

This is pretty much copy and paste from one of our previous projects. I removed some of the error handling (you have to check for the existence of the folder etc).

INSERTSOMEVIEWHERE is some view in Android. This code is basically meant to take a screenshot from a particular view ans save it in the gallery. You can take the root view if you want to take a screenshot of the whole app.

There is that external helper function directoryAndStorage.getOrCreatePictureDirectory I use to create a folder in the users gallery depending on which device we are running on (Some devices don't have an external storage and the Nook does not have the function getExternalStoragePublicDirectory). The helper function is far from complete, you could add support for different Android versions aswell:

public File getOrCreatePictureDirectory(String directoryName) {
    final File picturesDir;
    if (Build.PRODUCT.equals("NOOKcolor")) {
       // The nook color uses a slightly different path for images and the
       // usual constant for the path does not work
       picturesDir = new File("/mnt/media");
    } else if (Build.PRODUCT.equals("NOOKTablet")) {
       picturesDir = new File("/mnt/media");
    } else {
       picturesDir = Environment
          .getExternalStoragePublicDirectory(Environment.DIRECTORY_PICTURES);
    }
    picturesDir.mkdirs();
    File dir = new File(picturesDir, directoryName);
    if (!dir.exists()) {
       Log.i(Config.LOG_TOKEN, "'" + dir
          + "' does not exist, trying to create ...");
       if (dir.mkdirs() == false) {
         Log.e(Config.LOG_TOKEN, "Failed to create directory '" + dir
              + "'!");
         return null;
       }
    }
    return dir;
}

That's it so far. If you have questions, shoot. I'm going to post updates soon.

Hey, any update here? I'm hitting on the same wall, so some pointers would be great.