I think both the answers given so far are incomplete. You can give a microscopic answer to why pressure increases with depth with simplified models. I have written a lengthy post on this just now but I will list the main concepts here as well. Keep in mind that in the end all of the models, kinetic theory of gases as well as any continuum science are simplifications and approximations of an inherently complex nature. (In particular I share the view that physics are deterministic but we just do not have sufficient initial data. Thus in particular any probabilistic method is only a way to describe the missing information that we are simply lacking.)
Pressure on a macroscopic level
Interactions in actual fluids can be very complicated - a balance of contracting and repulsive forces that vary with distance of the particles from each other. This makes such phenomena very unattractive (and complicated) to model from a microscopic perspective. Somewhat surprisingly the macroscopic laws take the same form for dense liquids and moderately dilute gases. For instance the Navier-Stokes equations in their traditional form are valid in the continuum limit for Newtonian fluids. Liquids and gases only differ in terms of order of magnitude of dimensional numbers and equation of state. Both are nothing but viscous dampers.
Kinetic theory of gases
In the kinetic theory of gases you model the a gas as a multi-body system of particles interacting in collisions (or even complicated far-field interactions). For comparably simple elastic collisions one can find
$$\lambda = \frac{m_P}{\sqrt{2} \pi d^2 \rho}$$
for the mean free path where the density $\rho$ is coupled to the static pressure by the equation of state of an ideal gas
$$p \, v = \frac{p}{\rho} = R_m T.$$
This means that static pressure, which takes into account the hydrostatic pressure, is inversely proportional to the mean free path and thus with increasing pressure particles are more closely packed. They exert a bigger force on their surroundings as simply more particles collide with the wall (collisions happen more often).
Simple analogy for liquids
This simplified view can also be transferred to a solid where the spheres are so densely packed that they can't really be compressed anymore (incompressible fluid). The force and thus the pressure in between the particles increases as they are pressed together more strongly.
Misuse of incompressibility
An ideal gas law, incompressibility and hydrostatic pressure are incompatible concepts. If you fix the density (which is by definition of incompressibility) for an increasing static pressure (which is the natural consequence of hydrostatic pressure) the temperature has to increase as well, meaning particles would have to move faster in areas of higher pressure which would equilibrate and thus such a configuration would not be stable. This means a flow of an ideal gas with a large pressure gradient can never be assumed incompressible. Such a simplification is incompatible with the equation of state! Nonetheless the flow around a car might be assumed incompressible as hydrostatic pressure is approximately equal for all points and the change of static pressure due to dynamic pressure (Bernoulli's principle) is comparably small.
This is differently for liquids such as water where the governing equation of state is the Tait equation
$$p - p_0 = C \left[ \left( \frac{\rho}{\rho_0} \right)^m - 1 \right], $$
which clearly allows for large pressure ranges with small changes in density for the typical value of $m \approx 7$. As a consequence water can be assumed as incompressible over a wide pressure range.