Gate Logic Initial States?
The quick answer:  We don't know, and most of the time we don't care.

The long answer:  Manufacturers don't try to make the power-on behavior of simple And/Or/Not/Xor/Etc gates predictable.  Therefore, this behavior is not documented in any datasheets.  You might be able to measure the behavior, but you cannot say that "This AND-Gate does X, therefore all AND-Gates does X."  Different gates will behave differently.  It is even possible that the same gate behaves differently on different power-ups.

But let's consider the startup sequence.  Let's assume that the chip is rated for VCC=3.3v +/- 10%.  So below 3.0v, the behavior of the chip is undefined.  But the chip has some extra margin on the voltage, so it will likely operate at +2.9v.  So how long does it take VCC to go from 2.9v to 3.0v on power up?  It will vary from system to system, but it is likely longer than the propagation delay of the gate itself.  What does this mean?  It means that by the time VCC gets to within the proper operating range then the gate has come up and the output already reflects the current state of the inputs.

The only time that we actually care is when an output needs to be glitch free at power-up.  This is very difficult to guarantee normally.  Typically you would have to design some dedicated logic to guarantee this behavior.  In audio we do something similar to prevent pops on the audio outputs when power is turned on-- and we do it with relays to keep the outputs disconnected (and pulled to GND) until power is up and stable.