This all seems above board with these chips: the supply voltage for the logic part of the chip is 4.5V to 5.5V and the supply for the drive circuit is anything up to 36V.
The question I have is this: what about the ground connection? This chip has only one common ground for both Vcc connections - does this matter for my application? Would having a ground common to the Arduino and a motor coil potentially cause harm/unwanted effects with the Arduino? How would you generate the supply voltages required with a common ground?
There is only 1 ground for a reason. The term "common" ground is used to make it clear that multiple power sources SHARE "ground" potential in common. Unless you use some sort of galvanic isolation like opto-couplers, all voltages in a circuit must reverence their potential against a "starting" point (sorry can't think of a better word right now, maybe I should say it better that ground is a "reference" point for all voltages in a circuit). Without being tied together... the circuit reference points lose meaning... IE; things don't work. (Not to mention that you likely don't have a closed circuit in some cases)
So connecting the ground points should be used in your circuit especially because you have multiple voltage supplies... so MOTOR ground and ARDUINO ground are tied together in this case. (As it would for any other power sources you might add to your circuit.