My one of my gf's SPD cleats keeps loosening. The tension on her pedals is set plenty loose and the cleats are in ok shape, but every time I check the bolts they've loosened, so that's the only reason I can think of why she is having trouble getting out of the pedal.

Any tips for getting the cleat to stay put or any other theories about what's going on here?

Are the threads stripped?

I'd try grease. If the threads are dry, you won't be able to get the bolts tight enough and they'll loosen. For some reason, cleat bolts tend to be particularly prone to binding if they're dry. When that's the case, the bolt locks up against itself without ever really tightening down into the shoe. A couple of jiggles and it'll come loose.

So use plenty of grease and be careful not to tighten too much. They're also easy to strip.

I would go with blue loctite. Chances are, if the bolts are getting loose already, damage has already been done to the threads. The loctite will initially work like grease, so like lobster said, it will get the bolt seated. Once it hardens though, it will provide a little extra insurance against loosening.