How does gravity affect bullets?

The bullets don't hit the ground at the same time exactly because it is very difficult to fire horizontally, there is air resistance to account for, the ground may be sloped, there are Coriolis forces, etc.

Usually, when people refer to this phenomenon, they're referencing the principle of Galilean relativity.

You can read the famous excerpt from Galileo's book here. He considered sailing on a smoothly-sailing ship, and noted that if you're in the hull, you don't notice the ship's motion in any physics experiment.

Specifically, things seem to fall completely normally when you're in a moving ship. Someone standing on the shore watching would think that objects in the ship are falling in parabolic trajectories with constant forward speed equal to the ship's speed, but someone in the ship thinks thinks they fall straight down.

Now imagine two bullets. The first is dropped by someone on the ship. The second is fired from a gun on the shore, but fired at exactly the same speed as the ship's speed (it's either a slow bullet or a fast ship, or both). The bullets start out with exactly the same trajectory. They have no way of knowing whether they're supposed to keep up with the ship or the shore or what - they only know their location and velocity. So the two bullets must fall in the same way. By Galilean relativity, the bullet on the ship falls in the same amount of time as a bullet that's simply dropped, so the bullet fired from the gun falls in the same amount of time as a bullet that's simply dropped, too.

One way to view the math is as a consequence of Newton's laws of motion, which state

$$F = m \frac{\textrm{d}v}{\textrm{d}t}$$

If we transfer reference frames from the shore (frame S) to the ship (frame S'), we're transforming the velocities according to

$$v' = v + v_s$$

with $v_s$ the constant speed of the ship.

Then

$$F' = m \frac{\textrm{d}v'}{\textrm{d}t} = m \frac{\textrm{d}v}{\textrm{d}t} = F$$

so physics appears to work the same way in both frames (this assumes that mass is invariant).

However, the relativity principle is deeper than Newton's laws, and holds in theories of physics that are more fundamental than Newtonian mechanics, so it also makes sense to take relativity as more of a starting point than a consequence.

This is indeed true. The easiest way to think about it is in planes. You have horizontal and vertical planes for velocity and acceleration. For both bullets, there is initially no vertical velocity and the only net force acting upon them is gravity. You would then expect them to act similarly in the vertical plane, which is why they both hit the ground at the same time. There is nothing in the forward motion of the shot bullet that counteracts the pull downward from gravity (such as lift). I hope that explanation isn't too vague and helps you understand better what is going on.

EDIT: I should specify that this only holds true for ideal situations (being in a vacuum, no air resistance, etc.)

Mark came the closest in his answer, but I want to address some of the deviations from idealism in greater detail. People have mentioned the angle the gun is at and air resistance, so I'll try to touch on both.

You have a height $h$, say the velocity of the bullet is $\vec{V_b} = < V_{bx}, V_{by}>$ (add $t$ dependence when necessary). The time it takes to fall will be $\sqrt{2h/g}$ in a vacuum based on ideal Newtonian kinematics. The idea in the frictionless world is that the horizontal velocity of the bullet remains $V_p$ and the resultant velocity over time will be a combination of that and the vertical velocity caused exclusively by gravity, $g t$. I will use $<x, y>$ vector notation, and I'll just use a big vector arrow to indicate what is shorthand for a vector. For the other ball that just falls, I'll denote it $\vec{V_f} = <V_{fx},V_{fy}>$.

$$\vec{V_b}(t) = < V_p , -g t>$$ $$\vec{V_f}(t) = < 0, -g t>$$

Next, air resistance (drag) is usually taken to be some proportional relationship to velocity, in the opposite direction of the velocity vector. I'll take that relationship to be the common form of a constant times the magnitude of velocity squared (linearly $a_b = -C V^2$). Then I'll write the full differential equations for the problem... in some fairly extreme vector shorthand notation. Take $r$ to be the position.

$$\vec{a_b}(t) = -\frac{\vec{V_b}(t)}{|\vec{V_b}(t)|} C |\vec{V_b}(t)|^n = -\vec{V_b}(t) C |\vec{V_b}(t)|^{2} $$ $$ \vec{r_b}' = \vec{V_b}$$ $$ \vec{V_b}' = \vec{a_b}$$ $$ \vec{r_b}(0) = <0,h>$$ $$ \vec{V_b}(0) = <0,0>$$

A very good assumption for this experiment if it was performed at a small height (which is any height you could practically set up the experiment at), the velocity of the bullet will be much greater than the final velocity due to gravity. The convenient simplification that arises is:

$$|\vec{V_b}(t)| = (V_{bx}^2 + V_{by}^2)^{\frac{1}{2}} \approx V_{by}(t)$$

This allows a very nice closed form solution.

$$\vec{V_b}(t) = \left< \frac{V_p }{ C t V_p + 1 } , -g \frac{ \left( \frac{C t V_p }{2} + t \right) }{C t V_p + 1} \right>$$

From this, I can say the bullet will hit the ground at the same time as something dropped at the same time as firing when a certain condition is satisfied, which is:

$$ C t V_p \ll 1$$

Up until now I've used a non-standard drag coefficient. So I'll convert the equation to using the standard drag coefficient and then to ballastic coefficient.

$$ \frac{ C_d \rho A t V_p }{ 2 m} =\frac{ \rho t V_p }{ 2 BC} \ll 1 $$

So this is the first of my answers. For the other, I'll very simply address the angular sensitivity. The horizontal distance traveled by the bullet is much greater than the vertical distance it falls, but it still forms a triangle. We require that the displacement from the horizontal at the end of the flight due to the inclination of the gun must be much less than the height formally.

$$ V_p t \sin{\theta} \approx V_p t \theta \ll h$$

$$ \theta \ll \frac{h}{ V_p t} = \frac{1}{V_p} \sqrt{\frac{g h}{2}} $$

Say that the gun is at a height $h=20 m$. Bullet speed would fairly be $V_p=500 m/s$.

$$ \theta \ll 0.028 rad = 0.802^{\circ} $$

Note that this value is just a value sufficient to completely screw up the experiment so you would ideally want it 10x or more smaller than this. For the other part, dealing with the drag, I'll take some very general numbers. A drag coefficient for a generic cone is about $C_d = 0.5$, so I'll use that. For a bullet we'll say $m=10 g$. Air, $\rho=1.2 kg/m^3$. Bullet area we'll take as $A=0.2 m^2$. For 20 m height we have $t=2 s$.

$$\frac{ C_d \rho A t V_p }{ 2 m} = 0.006$$

So it seems my answer is that the gun must be held very still, but provided it's an "ordinary" gun and my numbers are correct, yes, the bullet will hit the ground at pretty much the same time. Hopefully I've formalized a little bit exactly when this is true.