How are Bitcoin Signed Messages generated? Ledger Nano S and other pieces of Bitcoin software and hardware can sign messages using the private key associated with an address.

Doing this, I get the following output:

-----BEGIN BITCOIN SIGNED MESSAGE-----
Test
-----BEGIN SIGNATURE-----
1BqtNgMrDXnCek3cdDVSer4BK7knNTDTSR
ILoOBJK9kVKsdUOnJPPoDtrDtRSQw2pyMo+2r5bdUlNkSLDZLqMs8h9mfDm/alZo3DK6rKvTO0xRPrl6DPDpEik=
-----END BITCOIN SIGNED MESSAGE-----


What exactly is being signed? How is the signature generated? What is the hash preimage that goes into the ECDSA signing algorithm?
The message that is signed is prepended with 

"\x18Bitcoin Signed Message:\n" + compactSizeEncoding( len(message) )


\x18 is Python syntax for unicode character 0x18. This new text string is then converted into a byte array by interpreting the string as UTF8. This will give you the correct hash preimage which is:

SHA256(SHA256(utf8.to_bytes("\x18Bitcoin Signed Message:\n" + compactSizeEnc( len(message) + message )) = 
559766ea41f2bc4125e5449200dbf7e902b724b66104820ca5b7fc59f30a19e0


You can see a Python code example here. The function msg_magic generates the hash preimage from the message. This Python code example does not correctly implement compactSizeEnc, however. So it only works with a message length up to 253 bytes.

The correct way of handling compactSizeEncoding is documented here.