How to make playlists for DLNA players?

I just set up a very similar box today (Debian, minidlna), and I had to work out some of these same issues. In my case, I am using an Onkyo stereo receiver as the client for audio files, and a Roku player for the videos and pictures.

Looking at your questions:

What format does the playlist need to be in?

The playlist file format is M3U (see https://en.wikipedia.org/wiki/M3U). This can be created by Windows Media Player and other similar tools.

One problem you will have to work out is that the M3U file generated by WMP usually includes the full path to the file (assuming that you have set up Samba on the Debian box and then mounted your music library as a network drive in Windows). Thus, the file will be something like G:\MusicLibrary\Artist\Album\Song.mp3, which is how Windows knows it. Unfortuately, since you're hosting this on Debian, the directory separator is different, there is no drive letter, etc., so Debian knows the file as /MusicLibrary/Artist/Album/Song.mp3.

This isn't much of a problem if you are familiar with Unix/Linux utilities like the sed editor. You can easily translate the filename from Windows format into Linux format. I used WMP to create the playlist, FTPd it to Debian, ran a simple sed substitution command to change the format of the filename.

Where must the playlist file itself be located, relative to the music?

I don't know if there is a "required" location. I initially put my playlists in the top level directory for my library (/MusicLibrary), and it worked just fine. I then created a dedicated directory /MusicLibrary/Playlists and put the playlist in there. Again, it worked fine.

After creating or relocating the playlist, I had to force minidlna to rescan the media files.

Should a file get renamed or moved, or tags edited, will the playlist be updated automatically?

If I understand your question correctly, it is actually two questions. If the file gets renamed or moved, the playlist will have to be manually updated. If the tags get edited, those are contained within the MP3 file itself, and the playlist points to the MP3 file, so you should be OK there. The only thing I can see is that there is an extended format option in the M3U file which allows song duration (mm:ss), artist, and title information to be stored in the M3U file. When you create the playlist, usually this information is extracted from the tags that exist at the time. If you update the tags, the information in the M3U file will not be updated to match.