If I need to use a 24V, 2.2A PSU (typical laptop charger) because I need higher voltage for a stepper motor, do I need to add anything else other than a 7809 or 7812 to power the Arduino?
E.g. do I need any additional parts, capacitors or just out of the 7809/7812 and into the Vin pin?
Draw us a diagram of the way you think the project would be wired up.
This will give us an idea of what you are trying to do and we can then supply some help.
If you simply want to trial this, your setup will work fine. Just put some 0.1uF decoupling on the regulator outputs.
For a long term effect, go with Heke's suggestion.
Adafruit only carries the 5V and 3.3V versions of the above, but it seems like I would want the 9V version (TSR 1-2490 http://www.adafruit.com/datasheets/tsr1.pdf) if I am going to connect it to Vin, right?
And I'm curious, other than heat and inefficiency, what is wrong with the 78xx regulators for this type of application? I see that they are terrible with large voltage differences between input and output, but are there other reasons not to use them?
If you know the approximate current draw, you can put a power resistor in series with the regulator input lead to handle some of the power dissipation.