RFC 3927 is the specification for how it should be implemented. It has a section 2.1. Link-Local Address Selection which specifies the usage of a PRNG and recommends that the PRNG should be seeded using the same initial value (e.g. a MAC address) every time.
PRNGs are deterministic – their only source of randomness comes from external seeds; reinitializing the same PRNG with the same seed will always give the same sequence of outputs (hence pseudo-random). So any APIPA implementation that uses a MAC address as its PRNG seed should also generate the IPv4 addresses deterministically.
The pseudo-random number generation algorithm MUST be chosen so that
different hosts do not generate the same sequence of numbers. If the
host has access to persistent information that is different for each
host, such as its IEEE 802 MAC address, then the pseudo-random number
generator SHOULD be seeded using a value derived from this
information. This means that even without using any other persistent
storage, a host will usually select the same IPv4 Link-Local address
each time it is booted, which can be convenient for debugging and
other operational reasons. Seeding the pseudo-random number
PRNGs are deterministic – their only source of randomness comes from external seeds; reinitializing the same PRNG with the same seed will always give the same sequence of outputs (hence pseudo-random).
It is not possible to know whether all APIPA implementations follow this recommendation except by testing them experimentally (many of them, such as the one in Windows, are closed-source). If I remember correctly, Avahi on Linux is compliant.
As one differing example, I seem to remember that the implementation used by Ubiquiti's airOS firmware is specifically called out in the device docs as directly using the device's last two MAC octets as the initial APIPA address (being somewhat noncompliant but nevertheless deterministic).