The solenoid coils can both have 5V on them. If they need higher current, do not power them from the Arduino 5V pin, you'll take out the 5V regulator, or blow the USB fuse.
Do connect the external supply's Gnd to the Arduino Gnd.
Use two N-channel parts, and two output pins. Which ever one has a high on it's gate will have current sunk thru it's coil to energize the solenoid, just what DVDDoug said.
Gonna make quite a clatter turning on/off 5 times a second.