Hmmm, well I also want to use the WiFi shield on one of the arduino's so SPI is also out of the question I suppose.
Why? The Ethernet shield also contains a SD card. Both are SPI devices, with different chip/slave select pins.
Would connecting via serial be accomplished via digital pins 0 and 1? I've yet to find a wiring diagram and sketch example of this.
Yes. Possibly because connecting RX to TX, TX to RX, and Ground to Ground is so simple that no one thought is necessary to draw you a picture.
I find it hard to believe that you can't find a sketch that shows how to write to, or read from, the serial port.
I suppose I could follow this example
Maybe. Blocked as spam for me.
Though this example should only allow one Arduino to send a message to the other and not allow bi-directional traffic, correct? I believe simply adding another cable between the two should allow for bi-directional traffic, no?
I don't know and yes.