How do I describe the order of events in spacetime? In Newtonian mechanics, we have 3-space and time. Time allows us to order events. For example, I hold a ball in the air at time $t_0$. Then I drop it at some later time $t_1 > t_0$. Finally it hits the ground at time $t_2 > t_1$. Thus, events are ordered by time. 
However, in special relativity, time is a dimension in the affine space. Furthermore, observers don't observe the same time necessarily. Therefore, it would seem we have lost our ability to "index" / order events. 
But without time, how do I describe the evolution of a particle in spacetime? That is, if a particle begins at one point in spacetime and moves to another, how do I describe this sequence of events? That is, the particle will be at some point in spacetime $\mathbf{x}_0$. I now need some way to index a "later" point at which the particle is at spacetime point $\mathbf{x}_1$. How do I do this? 
I suspect the answer is with proper time, but I am confused how this relates to regular time. I am so used to time indexing the order of events, I'm not sure what proper time tells me about when events actually happen. 
 A: The physics ("the description of the time evolution of a particle in spacetime") occurs on the backdrop of spacetime. i.e., coordinates like $(ct,x)$. Maybe (take $c=1$) the world-line of a particle satisfying some physics equation is parameterized by ${\bf x}(u)=(u-0.5\sin(u),0.1\cos(u))$. This is a line in spacetime, there's a timelike coordinate and a spacelike coordinate. The lines $(10u,0)$ and $(u,0)$ are different parameterizations of the same line. The second one, however, is an arc length parameterization. That is, it is not parameterized by the proper time. The weird sine/cosine line I defined is not an arc-length parameterization. To make it so, you'd have to find the proper time of the path and change variables from $u$ to the proper time $\tau$.
The proper time of this path, from coordinate $u_0$ to $u_1$, would be given by $\int_{u_0}^{u_1}\sqrt{\| {\bf x}'(u)\|^2} \mathrm{d}u$. The prime is differentiation with respect to $u$. The "norm" I define as $\|(t,x)\|^2=t^2-x^2$. So when I said change variables, the relation between $\tau$ and $u$ would be given by $\tau=\int_{u_0}^{u}\sqrt{\| {\bf x}'(k)\|^2} \mathrm{d}k$ for $u_0$ an arbitrary constant.
Two points in this spacetime, ${\bf x}$ and ${\bf y}$, can causally effect each other only if $\|{\bf x-y}\|^2\ge 0$ (timelike or lightlike connected), in which case it is meaningful to say that one of events $x$ and $y$ occurred before the other. The "first" one is the one with the smaller time coordinate. The condition that $\|{\bf x-y}\|^2\ge 0$ ensures that if $x$ comes before $y$ in one frame, it will come before in all frames. So you can order timelike connected events. You can't order spacelike connected events, and that's where your issue/confusion takes place.
To better understand this, maybe try the following exercises:
Define ${\bf x}(u)=(u-a\sin(u),a\cos(u))$ for constant $a$. Figure out, for what values of $a$, does this path represent a particle (moving at speeds less than the speed of light) and what values is the path unphysical (moving at speeds faster than the speed of light).
For the path above, try to fine $\tau$, and try arc-length parameterizing it. This might be difficult because I think it's an integral of $\sqrt{1-\cos(u)}$, but see how far that+wolframalpha gets you.
Prove that timelike connected events are ordered. That is, Lorentz transformations don't change the order of events.
Prove that spacelike connected events are not ordered. That is, Lorentz transformations do change the order of events.
A: You describe order of events in Minkowski spacetime exactly as you do for Newtonian physics with one difference: the events can only be well ordered if they lie in each other's past or future light cones. If the events have this relationship, then their order, as told by their time co-ordinates in any of their reference frames, is NOT observer dependent, even though the time intervals between them are observer dependent.
Indeed you can take this fact as the reason special relativity imposes the universal speed limit $c$. That is, we learn from special relativity that event order is observer dependent. Oh no! How does the principle of causality that causes must always come before their effects and which has never been experimentally seen to be violated survive this fact? Well it can't in general, but if we make the further postulate that events can only be causally linked if they lie in each others future / past light cones and the postulate that no observer can travel at a speed greater than $c$ relative to us, then this new, restricted causality is perfectly compatible with relativity: the order of such events cannot change between reference frames. There are other motivations, such as the requirement of infinite energy to accelerate any massive thing to a relative speed of $c$, but for me this the simplest and most powerful motivation: the speed limit exists to uphold our experimentally observed principle of causality. It's worth also witnessing that only a signatured metric, like the proper time interval, with one timelike co-ordinate can save causality in this way. A Riemannian universe cannot have even a restricted causality principle since in that case the order of all pairs of events is observer dependent.
Technically, this situation arises from the fact that the transitivity sets for the identity connected component of the Lorentz group (the so called, proper (volume form sign preserving), orthochronous (time interval sign preserving) Lorentz group $\text{SO}^{+}(1,\,3)$ for a given event are (1) the sheet of the two-sheeted hyperboloid $t^2-x^2-y^2-z^2=\epsilon^2>0$ that is contained within the origin's future light cone, (2) the other sheet of the same hyperboloid, contained in the past light cone and (3) the one sheeted hyperboloid $x^2+y^2+z^2-t^2=\epsilon^2>0$ contained in the elsewhere outside the cones. The image of an event in any of these sets stays in these sets under the action of $\text{SO}^{+}(1,\,3)$: thus if event $B$ is in the future or past light cone of event $A$, then the sign of the difference $\Delta\,t$ between their two time co-ordinates cannot change under any Lorentz transformation belonging to the identity connected component $\text{SO}^{+}(1,\,3)$. However, if $B$ lies outside the future/past light cones of $A$, then one can always find a proper, orthochronous Lorentz transformation that will change the sign of the difference between the two time co-ordinates.

Proof Sketch on Transitivity Sets
You can prove the above assertions by reasoning along the following lines: let event $B$ be in the future / past light cone of the origin and have co-ordinates $(t,\,x,\,y,\,z)$ where $t^2-x^2-y^2-z^2 = \epsilonˆ2 > 0$. Then $t^2=\epsilon^2+x^2+y^2+z^2>\epsilonˆ2$ where $\epsilon$ stays constant when $B$ is acted on by a Lorentz transformation. Thus we see that $t$ is excluded from the interval $(-\epsilon,\,\epsilon)$. Now act on the event with an element of the form $\exp(s\,X)$, where $X\in\mathfrak{so}(1,\,3)$ and $s\in\mathbb{R}$ varies continuously. Therefore, the time co-ordinate $t$ of the image of the event must move continuously with $s$ and therefore cannot jump the exclusion interval $(-\epsilon,\,\epsilon)$. On witnessing that any member of $\text{SO}^{+}(1,\,3)$ is a finite product of elements of the form $\exp(s_j\,X_j)$, we see that the image of $B$ is path connected to $B$ by a piecewise smooth path defined by each of the $s_j$ varying in turn from the value $0$ to their final, real values. Therefore, the image of $B$ cannot jump over the exclusion interval (which jumping would make the image a discontinuous function of one of the $s_j$). 
To deal with the case where $B$ lies outside the future / past light cones of the origin, so that $x^2+y^2+z^2-t^2=\epsilon^2>0$, impart a rotation to bring the co-ordinates of $B$ to the canonical form $(t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$. Now find a proper, orthochronous Lorentz transformation that will map $(+t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ to $(-t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$; the inverse of this Lorentz transformation then maps $(-t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ to $(+t_0,\,\sqrt{\epsilon^2+t_0^2},\,0,\,0)$ (exercise for the reader).
