Why is time different between different inertial observers? Suppose we have observer $A$ and observer $B$ that meet at a point $p$ when both of their clocks are zero. Why  after  that, the  measure of their clocks would be  different, since clocks depend on the laws of physics and the laws of physics are the same for all inertial observers? Shouldn't their clocks click at the same rate?
 A: It is true that the laws of physics being the same is one of the postulates of special relativity. However, there also is a second postulate which states that the speed of light is the same for all inertial observers, and this is the reason why time dilation exists.
Here is a way that I consider to be a somewhat intuitive explanation. Suppose we have a "stationary" observer A and a light ray that travels towards A. Another observer B travels in a straight line toward the light ray. Now, as measured from A, the light ray has some velocity $c$ which is the speed of light. However, B moves towards the light ray, so one would think that in B's frame, $c$ is greater. But since special relativity states that $c$ must be the same, this cannot be the case.
So the only possibility to "keep $c$ the same" for B (compared to A) is that time passes slower for B – this is time dilation. But now, as observed from A's frame, the light ray travels some distance in B's frame in some amount of time. Since B's time "passes slower", the distance that the light ray travels in B's frame is greater than it could be if $c$ were constant. And this is where length contraction comes into play – you can consider it, in some way, another "tool" to keep $c$ constant for both observers and from both observers' frames.
One should note that my explanation above is simplified and should not be taken too literally. However, it might help to get a simpler understanding of why time dilation and length contraction happens.
One could also add that both observers measure their own clock to run add the same speed, regardless of their velocity. They only measure each other's time to pass slower. Since both frames are equally valid, each observer measures the other observer's time to pass slower – time dilation is symmetric. See Time dilation all messed up! for a nice intuitive explanation.
TL;DR: It is due to constant speed of light.
A: In an entirely symmetrical situation, then yes you would be right that the clocks for $A$ and $B$ should tick at the same rate.
It could still be symmetrical that each observer sees the others time run slow when they are moving relatively to each other - in fact that is what relativity theory says does happen.
For the 'twin paradox' kind of questions where the observers then come back together after first synchronising clocks and one clock is behind the other - this occurs because the symmetry is broken.
$B$ might be the one that accelerates to change direction and return to $A$ for example, whilst $A$ remains inertial.  Then lots of maths would be needed to find the amount of time difference that occurs.
A: Einstein states: The light speed $c$ does not depend on the observer. Let's take this fact and consider the following two scenarios. In both cases the distance between the upper and lower mirror is $d$.

Observer A is stationary. Hence, the light travels the distance $s=2d$ in a single "round trip".
Observer B moves. However, now the light travels along the hypothenuse of a triangle. Using Pythagoras, we know that the travelled path is longer than in the stationary case. Doing the math you get the result shown in the picture.
If there is no information about the past available, we are unable to tell who is moving and who is at rest1. Hence, the two observers disagree about the reading on their watches: If there are several event, they might disagree which event came first, or whether two events happened simultaneously (=at the same time). This difficulty sits at the very heart of relativity theory, and one can understand why physicists had such a hard time accepting it in around 1905. However, since the two observers never meet again, it is impossible to decide who is wrong and who is right. Also note, the situation changes in the "twin paradox", because accelerations are involved. If one of two twins travels to mars and back, he/she experiences an acceleration. This acceleration breaks the symmetry. After returning to earth the astronaut is the "younger twin".

Footnotes:

*

*This is what Jonas calls "symmetric" in his comment.

A: 
Shouldn't their clocks click at the same rate?

To know whether two clocks tick at the same rate you need to somehow compare how long it takes for the two ticks. This question presupposes there is some absolute notion of time in which you can do this comparison. But relativity got rid of the notion of absolute time. Without it, how would you even determine what is their "rate"?
As you said, physics is the same for both observers, thus if you magically switched them, they would never notice any difference in physics around them. Their local physics in their lab is still the same and their clocks tics the same.
The different rate they see is relative to their inertial reference frame and this is frame dependent. Time rate is given by projection of objects 4-velocity onto observers "time forward" direction. But two different observers have different notion of what this "forward in time" direction is and thus their projections are different.
Their time direction is in the direction of their own 4-velocity. This is kind of obvious, because in your own rest frame, you are not moving in space, only in time, thus whole 4-velocity has only time component. So when observer A claims observer B times is slower, he means observer B moves with different speed in the direction observer A considers to be "forward in time". And this depends on the observer.
This is analogical to two cars going in different directions, but with the same speed and asking who moves forward with the greatest velocity? From the point of view of Car A, it moves only in forward direction, thus its forward speed is its overall speed. But it sees car B moving in different direction and once it projects its velocity onto its own forward direction, it will claim car B does move in forward direction more slowly. But from the point of view of car B it is B that moves forward not A and it will project velocity of A onto its own forward direction and will claim A moves in forward direction more slowly. The reality is they both move forward the same in their respective point of views, they just cant agree on what it means to go "forward".
Situation changes only a little when two observers are not inertial and they meet again at some point, say by observer A rotating and returning back. Once they are at the same spot, you can compare their clocks and they will show different times, which is absolute statement. The different time is then given by integral along their whole trajectory. I already said, that the clocks ticks the same in their respective frames, so the overall time that passed on the two clocks is given by "length" of their trajectories in spacetime. If "length" of the trajectory of observer A is less than "length" of trajectory of observer B, then A will come to the meeting point younger.
The "length" of time-like trajectory is quantity fully analogical to ordinary spatial "length", it is just adjusted for time-like directions instead of space-like and behaves a little differently. The main difference is that, while in Euclidean space the hypotenuse of triangle is smaller than sum of the sides, for time-like curves in spacetime it is opposite, the hypotenuse is longer than sum of the sides. So while in Euclidean space the shortest path between two points is straight line, in spacetime the straight line connecting two time-like separated events is the longest. This is important for correctly predicting twin paradox, because the twin at rest moves on the longest path (i.e. on a straight line) to the meeting point and thus will be older.
A: Quick answer; two different inertial paths can have different elapsed proper times.  Consider one object in orbit around a planet, crossing paths (twice) with another launched from the surface, meeting it and comparing clocks on the way up and the way down.  There is no reason to expect their proper times to be identical in this case (since both the radius of orbit and the upward launch speed are unspecified, and therefore arbitrary).
