It generally doesn't. As far as I know, currently there is no widely accepted mechanism for making this work (aside from DHCPv6, obviously), only manufacturer-specific hacks.
The most likely guess I have (though it still doesn't entirely match up with which operating systems you report working):
Some router DNS/DHCP software, such as dnsmasq, tries to guess the SLAAC-derived address (but specifically just the EUI-64 format address) for each device which obtains a DHCPv4 lease. Since the DHCPv4 server knows the host's MAC address, that's all it needs to derive the EUI-64 SLAAC address.
For example, the dnsmasq documentation for the dhcp-range option (which controls DHCPv4, DHCPv6, and SLAAC at the same time) says:
ra-names enables a mode which gives DNS names to dual-stack hosts which do SLAAC for IPv6. Dnsmasq uses the host's IPv4 lease to derive the name, network segment and MAC address and assumes that the host will also have an IPv6 address calculated using the SLAAC algorithm, on the same network segment. The address is pinged, and if a reply is received, an AAAA record is added to the DNS for this IPv6 address. Note that this is only happens for directly-connected networks, (not one doing DHCP via a relay) and it will not work if a host is using privacy extensions. ra-names can be combined with ra-stateless and slaac.
This obviously can't work with RFC 7217 opaque SLAAC addresses which you'll get from NetworkManager or dhcpcd(it does SLAAC), nor the ones generated by Windows 10, though it should work with Android and the Linux kernel's built-in SLAAC support.
(It is in theory possible that some routers could do something similar based on their neighbour cache – e.g. if they see a particular MAC address speaking as 2001:db8::1234, they might automatically associate it with the corresponding DHCPv4 lease and the hostname... This would be a bit unreliable and wrong and I hope your router doesn't do this, but it still wouldn't be the worst thing I've seen home routers do with their DNS.)
Other guesses:
Hosts can indeed advertise DNS records on their own. All Windows clients support performing DNS updates on their own (RFC 2136), which also works without Active Directory as long as the authoritative server accepts updates without any authentication. It is possible, though I've never seen this, that your router actually accepts DNS 'UPDATE' messages from LAN devices and uses them to update its own DNS.
Linux devices almost never do this automatically. Still, it might be worth trying to run nsupdate against your LAN domain to see if it works.
It wouldn't be entirely surprising – though again, I have never actually seen this in practice – if the router's DNS server acted as a proxy for mDNS and/or LLMNR (the two multicast name resolution protocols often found on LANs).
Non-options:
I was also expecting there to be a "host name" or "FQDN" option which could be sent by hosts in ICMPv6 Router Solicitations, but there isn't one.
ICMPv6 does have "Node Information Request" packets which can be used to query the hostname, but no OS implements responding to them, so it's very unlikely that a router would use them.
