Also I want to run a appliance off the same power supply. How can this be done?
That's kind-of confusing, but yes, you could build a box with an Arduino and power supply inside. That box can plug into the wall and it can have a 120V power-outlet that's controlled by the Arduino.
So for example, you could plug a 120V lamp into that box and control the lamp with the Arduino. I've built some sound activated lighting effects that work that way. My project has a box with an Arduino and power supply inside, except the relays are in a separate box, connected by a cable. I built my own power supply from a transformer, rectifier, voltage regulators, and capacitors. I also build by own solid state relays.
I was thinking Main power supply> To a voltage regulator to step down the voltage>Arduino>RelayRelay is hooked to that same power supply To appliance>Back to main power supply.
But I was thinking if I hooked up a appliance to the relay and turned on the appliance. Wouldnt my arduino just fry?
As long as you wire it correctly, it wont' fry. A relay is an electrically-controlled, electrically-isolated switch. So, there's no electrical connection between the relay contacts (120V) and the relay coil.
Most relay coils require more voltage and/or current than you can get from an Arduino I/O pin so you generally need a transistor or MOSFET driver circuit. But, you can buy a "relay board" that has the driver circuit built-in. Or, you can find solid state relays that can be directly controlled by the Arduino. (I believe the Power Switch Tail is a solid state relay).
I was thinking Main power supply> To a voltage regulator to step down the voltage>Arduino>
You can get a ~12VDC or 5VDC power supply. The Arduino has an on-board 5V regulator.[/b] If you look-up the specs, the "recommend operating voltage" is 7-12VDC. Or, you can bypass the regulator and run it from 5VDC.