When running a fresh ROM, the APN settings are defined by the SIM card inserted, downloaded from the network via some handshake protocol or are they predefined in the rom for each network ?
They are included in Android. The correct settings are determined by your SIM MCC and MNC (Mobile Country Code and Mobile Network Code). If you want, you can view the list of preset APNs by looking at the source code, for example at android-source-browsing.
The file name in this case is /etc/apns-full-conf.xml, but apparently it varies.
Next to the pre-configured settings from
/etc/apns-full-conf.xml as described in onik's answer, some providers offer to send you so-called "service SMS" for an automated configuration. Opinions on those are quite confusing: Some say those do not work on Android or iOS devices, and you'd have to enter APN data manually (e.g. Simyo in Germany), while others even let you select your device in advance to send you a tailored service SMS (e.g. T-Mobile Gernamy, where I selected an SGS3 and then was asked to enter my phone number to receive the SMS; or Base Germany, which is the same provider/network as Simyo; one might say that's due to the fact that Simyo is a discounter brand).
I'm with mentioned provider named Base (belonging to the E-Plus group). When I got my new Optimus 4X, inserted the SIM, and started it, I immediately got 3 Service-SMS, which were "executed" on my device. I unfortunately did not check the configuration before, so I cannot say what effect they had (if any) -- but at least I've got no error messages, and everything was working fine.
Edit: Comments from onik (on his answer) and Compro01 (here, see below) indicate: whether those "service SMS" do work or not, might well depend on the (device and) ROM used.