Moschatus Is it normal to have to search for APN data online and then enter it manually?
Semi-normal -- carriers and others post APN data, and the OS has an APN editor, because sometimes it's necessary.
Moschatus Would it also be missing on the stock ROM?
Maybe. It's hard to say without trying.
Moschatus Would it make a difference if the device were logged into the mobile network with the stock ROM before installing GOS?
No. APN information does not survive across an OS installation (almost nothing does).
Moschatus Doesn't the APN data normally come with the firmware?
A "carrier configuration" database is part of the OS (not part of the firmware).
Moschatus I use the RethinkDNS app. Could something be blocked that is needed to obtain the APN data?
Unlikely, unless regular GrapheneOS system updates are blocked.
Overall, unless you were to disclose which Australian carrier(s) you had trouble with and somebody were to dig around in carrier configuration databases, it's hard to know what went wrong.