What you need is an LDO (Low DropOut) regulator. The Micrel MIC2937 has a dropout of only 370 mV at 750 mA out.
You'll have to check the output voltage of the adapter at maximum current. Connect a 16 \$\Omega\$/10 W resistor and measure the voltage. You can combine resistors you have in your box, keeping in mind that P = V\$^2\$/R. The voltage should be higher than 12.4 V.
The MIC29372 (same datasheet) is a version with adjustable output, which may be of help if the output voltage isn't high enough for 12 V out.
edit
If the voltage is too low, and you really want to use the adapter, you can replace the rectifier diodes with Schottky types. That will give you an extra volt output.
edit 2 (regarding the LM317 hli also proposes)
If it's a 12 V adapter it will deliver about 12 V under load. Saying that the unloaded voltage is high enough for the LM317 is meaningless; you do want to use it, don't you? 12 V, even a bit higher is insufficient for the LM317. Don't design for unreliability and use an LDO.
edit 3 (2012-06-14, re your comment)
If the adapter is only going to be used only for powering a relay you don't need a regulator. The relay will only show a small load to the 12 V, so it may well be a few volts higher (unloaded transformers output a higher than nominal voltage). This relay is rated at 12 V, but has a maximum voltage 1.7 \$\times\$ that, so that's 20.4 V, which should be safe. Nominal power is 360 mW, and that will be somewhat higher at 15 V for instance (560 mW). If the voltage at 30 mA load is much higher than the 12 V you could still use a regulator. This will also consume some power, but the sum of regulator and relay power would be less than the relay alone.
Also nice about it is Must operate voltage, which is maximum 75 % of rated voltage. That means it will still work if the adapter's voltage would drop a few volts. The Micrel regulator will drop less than 200 mV at 30 mA, if we go for the adjustable, and choose 10 V out, then we will have proper regulation down to 10.2 V in, and the relay will only consume 250 mW instead of 360 mW. So we win twice.
Best Answer
First, you need to go back to the datasheet for the regulator. There is a specification for minimum output load current. My recollection is that value is 5 mA.
That current determines the value of the resistor connected from the output of the regulator to the Adj pin. R3 & R9 in your schematic diagrams.
1.2V / 5 mA = 240 Ohms. Note that 240 Ohms is used in all of the app notes for the regulators.
Note that you can now treat the regulator Adj pin (with that resistor installed) as a current source. The output voltage is the voltage across the resistor from the Adj pin to ground PLUS 1.2V. Because there is a constant 5 mA current from R3, it's easy to calculate the value of the resistor to ground.
Note that the value of R3 & R9 can be changed to make things easier for you. 240 Ohms is the highest value you should use but you can safely go lower. This may make it easier for you to pick a pot value that is more readily available.
Also note that your negative regulator can't be the same as the positive regulator unless you use separate unregulated supplies. The negative regulator would need to be a LM137 (or LM337), not a 117 or 337.