GND/Vss of 2 circuits with independent power supplies, and usage of scope/logic-analyzer
You need to connect your logic GND probe to the ground of both circuits.  

This also means that both circuits will have their grounds connected, but in this case it's okay as one is powered by a battery and is completely independent (relative to mains/wall wart)  

You couldn't do this if one of the circuits had a ground reference higher/lower relative to the other's (or indeed if either of the circuits have a different ground reference to the logic probe GND)  

Remember that voltage is always relative between two points. This means you can never say something is just e.g. "5V", rather "5V relative to x". In practice we often just say "5V" as we assume that the reference point is known.
This means that the reference point (usually the point we call "circuit ground", or "0V") can be different relative to another and still be called "0V". This does not have to be the earth (i.e. the stuff we stand on), or "safety ground" - obviously battery powered circuits have a circuit ground which is (usually) not connected to the earth. 

I tried to find a decent reference that explains all this better than I can but I couldn't come up with a satisfactory one. I'll maybe add some more later if time permits - the basic answer though is yes, you need the GND probe connected to both circuit grounds (i.e all connected together)

EDIT - Here is some more to try and make things a bit clearer:

I threw together a simple circuit which roughly corresponds to the setup in the question:



V2/Rx_Circuit represents the Rx circuit and output, and V1/Tx_Circuit represent the Tx_circuit and output.
V_noise and Cpar/Cap2 represent typical mains coupling from surrounding power leads, etc.
Notice the probe ground lead is connected to the Rx circuit ground, but not the Tx circuit ground.
So what happens if we try to probe the Tx Circuit output? We can see the probe tip is attached to the output - here are the simulation results:  



What we can see is the mains noise capacitvely coupled onto the Tx circuit output, along with a bit of the Tx output. The Tx output is 1KHz a square wave set at 3.3V, so obviously this is no good.  

Out of interest to see how accurate the simulation was, I grabbed a battery powered proto  with a 3V square wave output at around 1kHz which (very) conveniently happened to be sitting on my desk, and ran the test for real.
All I did was attach the scope tip (set to x1 so it has the same 1 Megaohm impedance as the sim) to the output, but not the ground lead.
Here is a picture of the result:



For such a rough SPICE simulation which does not allow for many factors, it doesn't seem to be too far off (V/div is 50mV, so the signal is ~200mV pk/pk)  

The way to fix this is obviously to connect the probe ground lead to the Tx circuit ground so there is a low impedance return path (a circuit always has a current loop)
Without it there is only the capacitive coupling which will only let high frequencies through .This is why the 3.3V Tx_signal comes through as strongly as the much higher voltage mains, as the rise time of the square wave is much faster than the slow 60Hz mains.

It's worth experimenting in SPICE and real life with things like this till you get the idea of what's really going on. Most schematics don't include things like parasitic capacitances/inductances/resistances which can throw a spanner in the works if you are not prepared for them.