I'm unsure what the general solution for Windows is. But executables that are built that rely on the shared libraries cannot run if the dll's aren't either in the system path or in the same directory as the executable.
I guess the solution closest to the gnu conventions would be to install the dll (and the dll.a?) in the "system path".
That might be, but I know of no project doing that (you'd run into all sorts of security issues).
It might make some sense to install it in the same directory as the few nettle executables, but that won't solve everything. E.g., with regards to gnutls, you'd need the nettle dll located in the same directory as the gnutls executable, which nettle doesn't know about; it may or may not be the same directory as nettle's $bindir. So you'd probably need to copy it around anyway.
Perhaps it'd be useful to ping other projects and get their take? It couldn't know about it, that's right, b/c you'd need to build and install nettle before gnutls. But gnutls could know about nettle and install to the same location (pkg-config really helps here). But really it's the person doing the build that should have the discretion to place the files where they want. The --sharedlibdir idea would work for me. By default it could point to --libdir.
A related question is how to run the testsuite using the4 shared libraries; do you need to copy the dlls into the subdirectories with executables which are run by the testsuite, or is there anything analogous to LD_LIBRARY_PATH (which is used for running the testsuite with ELF shared libraries).
On Windows, you can either copy the dlls into the exe's directory or put the dll's directory in the front of the "PATH" env var. The easiest thing to do is to copy it (windows doesn't do soft links) and then use relative paths for everything so you don't run into issues with unix-style paths vs. windows-style paths (/bin/ vs C:\msys\bin).
When I tried it, autoconf seemed to not be included in the msys installation. But I don't remember much of the details.
You have to put together your own msys system -- using their old installer didn't provide you with all the tools that you can get directly from the sourceforge page. The msys/mingw folks are working on a solution through their "mingw-get" application. I personally use a batch file I wrote to download and setup my environment. I'd be happy to point you to a place where you can download it for your own use.