A lot of people really don't understand GPGME and it probably doesn't help that the documentation that exists is basically the code commentary written at the time. It will, however, allow complete or near complete programmatic access to the entire GNU Privacy Guard suite and is supposed to also enable access to things like libassuan, gpg-agent and various other components. Which is why by default it also includes the S/MIME implementation which almost no-one outside of a few companies that exclaimed loudly in the late '90s use.
Currently GPGME includes something like 500 separate functions or more and definitely covers pretty much anything you'd do with GPG on the command line. It does, however, also contain some relics of previous design choices which have been subsequently determined to be not the right direction. For example, this is an API with large chunks of GTK 2 in it. Obviously, this needs to go (and it will when time permits). Another problem it has these days, perhaps the biggest hurdle to adoption is that when someone says "API" most coders don't immediately think of C header files to compile in with their own code in order to access the thing; let's face it, these days most people are thinking of something that's RESTful or at least let's them interact with data in a JSON format. GPGME is about as far from that as it's possible to get. Note that while it ought to be possible to make it play nicely with JSON, it can never be RESTful because editing keys can't be. Plus managing keys via the web is just asking for trouble.
There are also a lot of undocumented features and aspects of the thing such that even people working with the software since its inception can still be surprised by some things. Like, say, the XML format for keyring data that had everything except a formal schema (until that was generated a couple of months ago).
On the other hand, for all the good things Mutt does, it also does some rather shocking things. For example, whether GPGME is used or not, there should be no reason at all for Mutt to cache passphrases; in either scenario it ought to be handed over to GPG (with or without gpg-agent). Likewise, it ought to be honouring the configuration parameters in the ~/.gnupg/gpg.conf file (and others in that directory). Sure, setting an alternate key ID for different accounts to change the way the commands are called or even being able to specify alternative config files or whole directories (e.g. gpg --homedir ~/.gnupg-work/gpg.conf). As things stand, however, Mutt wastes time trying to solve problems that are already solved by the program it interacts with, like passphrase or key management, but doesn't allow access to the normal features of GPG, many of which are fantastic for email like using group lines for either multiple recipients or to override key selection for particular recipients (because there's always that one guy who keeps losing his secret key or forgets the passphrase and now you've got 15 public keys with the same address as the UID and the default behaviour is to pick the first match which is very likely not correct). Emacs is a little better there, but even it fails to pick up on the gpg.conf file which usually automatically answers the things it wants to prompt for.
Now, for something a little more useful and tangentially related, GPGME comes with another nifty little undocumented thing called gpgme-tool. It's a rudimentary interface to GPGME which will run on a UNIX socket (and of course you could use ncat or something to make it sit on a network port if you wanted). Though it is undocumented it is fairly self explanatory if you run it and interact with it for a little while and begin with the help command. Alternatively this works pretty well:
echo help | gpgme-tool > gpgme-tool-cheatsheet.txt
It'll happily do all the basics (encrypt, decrypt, sign, verify, change passphrases, generate keys, list keys, list secret keys, search for specific keys or select them, etc.). If you want to see the "hidden" XML format try this:
echo "KEYLIST --secret-only" | gpgme-tool > secret-key-list.xml
That won't export the secret keys, just list them and data about them. Also, it'll export with some output format cruft that will need to be filtered out before anything will really recognise it as XML (delete the top line, the first two characters of each subsequent line and the %0A from the end of each line). Anyway, gpgme-tool may give a better idea of what GPGME can really do. The PyME Python bindings for GPGME, for instance, attempts to automatically match GPGME functions (and usually achieves that without trouble); the current list of features in pyme.core.pygpgme comes to 534. Compare that to the command line and GPG 1.4.20 has 322 options, while 2.1.11 has 347 (I skipped 2.0 so I can't check, but it should be somewhere between those two).
As for the previous answer referring to matching the key commands, that should be solely driven by the configuration options and whether or not Mutt "allows" full access to GPG or not. I'm currently using Mutt with GPGME and the two functions mentioned (mail-key and extract keys) are fine, although Mutt does have trouble recognising PGP/in-line content if it has assigned or picked up the text/plain content type from somewhere. When that happens then yes, it is usually necessary to switch to Emacs or something. Still, that appears to be an issue with the way Mutt checks whether content really is just text or how it otherwise checks for OpenPGP format content. While I'd love nothing better than to just say we should all be using PGP/MIME instead (and we should be), unfortunately a lot of people stick with in-line because they want to (e.g. users of The Bat! on Windows) or need to (e.g. they need to send encrypted email from an Android device).
Basically it looks like Mutt relies solely on the message being multi-part MIME with one or more of those parts containing the key, signatures and/or encrypted content for it to do anything with. It won't just search through any plain email looking for content that matches, but that's neither GPG's nor GPGME's fault. The solution is to either add those features to Mutt or open the message in something with that capability (e.g. Emacs with EPA/EasyPG, which should be enabled by default these days) or pipe the message out to a direct command (or gpgme-tool if you like, but when piping it's generally easier to go straight to a regular command).
As for GPGME, not everyone has it available because it always needs to be compiled from the same source version as is installed on the system. If you upgrade GPG and don't recompile GPGME to match then there will likely be problems. On the other hand installing GPG from source is usually recommended where possible, so if going the GPGME route it becomes good practice to just run that recompile when updating GPG and it should all be fine.
Whereas those people who rely solely on the packages provided by their chosen distribution will also be subject to whatever the maintainers of those packages can be bothered maintaining and they may or may not always understand the requirements of GPG and GPGME working together. For example the MacPorts package for GPGME is set to depend on GPG 2.0.x, which in turn is set to conflict with GPG 2.1.x, so most people installing 2.1 can't also install GPGME, even though they clearly do work together. Getting GPGME to work in that scenario requires doing things that MacPorts recommends against (compiling things outside of the port management system, but within /opt/local). Some Linux distributions may have similar issues.
So if you're only going to be using PGP/MIME there should be no problems with using the GPGME integration and it will mean you never have to configure specific commands into your .muttrc file. If you deal with PGP/in-line then you're going to encounter problems, but they can't be avoided either way with Mutt so I'd recommend using GPGME if you can anyway.
DISCLAIMER: I'm involved with dev work to make an API to the API for all the non-C devs to be able to use the thing post-overhaul. I also ported PyME 0.9 from Python 2 to Python 3 (it's currently in a branch of GPGME and only the Python 2 version is available via PyPI and pip).
UPDATE: that port of PyME to Python 3 is now in the master branch of GPGME and available on PyPI as pyme3.
Best Answer
In order to do this, add this line to your ~/.gnupg/gpg.conf file:
keyserver <keyserver address> keyserver-options auto-key-retrieve