I have a relatively simple setup consisting of an Arduino nano connected to a standard 5V relay module, and then a motor being switched by the relay. The circuit works fine when the motor does not have power, but as soon as the motor is connected and powered, the Arduino becomes frozen. No aspects of the code work, Serial communications stop, and it is only fixed by resetting the Arduino. The motor and Arduino are being powered by separate sources, but they share a common ground connection. Help!
This is very common it is caused by interference from the motor.
Remove the common ground, make sure there is a kick back diode across the motor put a small 0.1uF ceramic capacitor as close to the motor’s brushes as possible.
Also there's the power draw. Sometimes people forgets that Arduino can only have so much draw without an issue. The USB power is limited to max 500mA and external power regulator can have a bit more but if a motor draw is more than that, it will cause brownout and the chip will crash.
True but in this case he does say:-
The motor and Arduino are being powered by separate sources,
Hi,
Welcome to the forum.
Please read the first post in any forum entitled how to use this forum.
http://forum.arduino.cc/index.php/topic,148850.0.html
What is the motor specificetions and what are you using to supply it with power?
Can you please post a copy of your circuit, in CAD or a picture of a hand drawn circuit in jpg, png?
Thanks.. Tom.. 
I am not sure of the exact motor specifications, as it is a toy motor which came out of a nerf gun. Best guess is that it is meant to be powered by 6 volts from 4 AA batteries. In my current setup, I am using 4 AAs to supply it power, just like in the stock gun. Attached is a schematic drawing of the setup.
Remove the ground wire between the two supplies.
It has no function with two supplies and relay isolation.
Use a kickback (back-emf) diode across the motor terminals.
Leo..
Quite right, as advised in reply#1 - OP have you tried that yet? If not why not? You came here asking for advice and you seem to be ignoring it, why?
I intend to try it tomorrow... Sorry, family complications have delayed my work on this project. 
Sorry Mike, missed that post.
Leo..
jjpauls:
I intend to try it tomorrow... Sorry, family complications have delayed my work on this project.
Sorry about that, but you did have another post after that information, it would have been good to acknowledge it and mention the delay in implementation.
Grumpy_Mike:
it would have been good to acknowledge it and mention the delay in implementation.
Ok, I will take note for future situations.
Update on the project: I have removed the common ground and added a flyback diode on the motor terminals. For now, the project is working perfectly, but it is currently held together with jumper wires. The next step is to make it permanent and then give it a final test. I would seem that you have solved my issue; thank you everyone!