Connecting two different microcontroller outputs together to drive a single device?
It depends on the output circuit of the device you are trying to hack. The solenoid is probably wired (like a relay) on one end to the positive supply and to ground through a transistor on the other (or a driver chip like ULN2003).

I would put a second transistor in parallel with the existing one and control it from my device.

The solenoid would be driven whenever any of the devices would like it on, however it would not turn off unless both devices want it off.

If your "add-on" must have the ultimate authority, than you can cut the output trace and just wire the existing output to any input of your device.