You are asking to compute the double quotient $B\backslash G /B.$ This is the same as computing $G\backslash (G/B \times G/B)$. A point in $G/B$ is a full flag on $k^n$. So you are trying to compute the set of pairs $(F_1,F_2)$ of flags, modulo the simultaneous action of $G$.

Another way to think about $G/B$ is that it is the space of Borel subgroups (the coset of $g$ corresponds to the conjugate $g B g^{-1}$, where $B$ is the upper triangular Borel that was fixed in the statement of the question). The passage from flags to Borels is given by mapping $F$ to its stablizer in $G$.

So you can also think that you're trying to describe pairs of Borels $(B_1,B_2)$, modulo simultaneous conjugation by $G$.

Now recall that a torus $T$ in $G$ is a conjugate of the diagonal subgroup. Choosing a torus in $G$ is the same as choosing a decomposition of $k^n$ as a direct sum of 1-dimensional subspaces (or lines, for short). (These will be the various eigenspaces of the torus acting on $k^n$.) The diagonal torus corresponds to the standard decomposition of $k^n$ as $n$ copies of $k$.

Now a torus $T$ is contained in a Borel $B$ (let me temporarily use $B$ to denote any Borel, not just the upper triangular one) if and only if the corresponding decomposition of $k^n$ into a sum of lines is compatible with the flag that $B$ fixes, i.e. if the flag is given by taking a sum one one line, than that one with a second, then that one with a third, and so on. In particular, choosing a torus $T$ contained in a Borel $B$ determines a "labelled decomposition" of $k^n$, i.e. we may write $k^n = L_1 \oplus \ldots \oplus L_n$, where $L_i$ is the $i$th line; just to be clear, the labelling is chosen so that the corresponding flag is just $L_1 \subset L_1\oplus L_2 \subset \cdots.$ (Again, to be completely clear, if $T$ is the conjugate by $g \in G$ of the diagonal torus, then $L_i$ is the translate by $g$ of the line spanned by the $i$th standard basis vector.)

Note that this labelled decomposition depends not just on $T$ (which only gives an unlabelled decomposition) but on the Borel $B$ containing $T$ as well. (In more Lie theoretic language, this is a reflection of that fact that a torus determines a collection of weights in any representation of $G$, while a choice of a Borel containing the torus lets you order the weights as well, by determining a set of positive roots.)

Of course, $B$ will contain more than one torus; or more geometrically, $k^n$ will admit more than one decomposition into lines adapted to the filtration $F$ of which $B$ is the stabilizer. But if one thinks about the different possible lines, you see that $L_1$ is uniquely determined (it must be the first step in the flag), $L_2$ is uniquely determined modulo $L_1$ (since together with $L_1$ it spans the second step in the flag), and so on, which shows that any two tori $T$ in $B$ are necessarily conjugate by an element of $B$, and the same sort of reasoning shows that the normalizer of $T$ in $B$ is just $T$ (because if $g \in G$ is going to preserve both the flag and the collection of lines, which is the same as preserving the ordered collection of lines, all it can do is act by a scalar on each line, which is to say, it must be an element of $T$).

Now a key fact is that any two Borels, $B_1$ and $B_2$, contain a common torus. In other words, given two filtrations, we can always choose an (unordered) decomposition of $k^n$ into a direct sum of lines which is adapted to both filtrations. (This is an easy exercise.) Of course the ordering of the lines will depend which of the two filtrations we use. In other words, we get a set of $n$ lines in $k^n$ which are ordered one way according to the filtration $F_1$ given by $B_1$, and in a second way according to the filtration given $F_2$ by $B_2$. If we let $w \in S_n$ be the permutation which takes the first ordering to the second, then we see that the pair $B_1$ and $B_2$ determines an element $w \in S_n$. This is the Bruhat decomposition.

It wouldn't be hard to continue with this point of view to completely prove the claimed decomposition, but it will be easier for me (at least notationally) to switch back to the $B\backslash G/B$ picture.

Thus consider the coset $gB$ in $G/B$, corresponding to the Borel $g B g^{-1}$. Let me use slightly nonstandard notation, and write $D$ for the diagonal torus; of course $D \subset B$. We may also find a torus $T \subset B \cap g B g^{-1}$. Now there is an element $b \in B$, determined modulo $D$, such that $T = b D b^{-1}$. (This follows from the discussion above about conjugacy properties of tori in Borel subgroups.) We also have $g D g^{-1} \subset g B g^{-1}$, and there exists $g b'g^{-1}\in g B g^{-1},$ well defined modulo $g D g^{-1}$, such that $T = (g b'g^{-1}) g D g^{-1} (g b' g^{-1})^{-1} = g b' D (b')^{-1} g^{-1}.$

We thus find that $b^{-1} g b' \in N(D)/D$, and thus that $g \in B w B$ for some $w$ in the Weyl group $N(D)/D$. Note that since $b$ and $b'$ are well defined modulo $D$, the map from $T$ to $w$ is well-defined.

Thus certainly $G$ is the union of the $B w B$. If you consider what I've already written carefully, you will also see that the different double cosets are disjoint. We can also prove this directly as follows: given $B$ and $g B g^{-1}$, the map $T \mapsto w$ constructed above is a map from the set of $T$ contained in $B \cap g B g^{-1}$ to the set $N(D)/D$. Now any two such $T$ are in fact conjugate by an element of $B \cap g B g^{-1}$. The latter group is connected, and hence the space of such $T$ is connected. (These assertions are perhaps most easily seen by thinking in terms of filtrations and decompositions of $k^n$ into sums of lines, as above). Since $N(D)/D$ is discrete, we see that $T \mapsto w$ must in fact be constant, and so $w$ is uniquely determined just by $g B g^{-1}$ alone. In other words, the various double cosets $B w B$ are disjoint.

The preceding discussion is a litte long, since I've tried to explain (in the particular special cases under consideration) some general facts about conjugacy of maximal tori in algebraic groups, using the translation of group theoretic facts about $G$, $B$, etc., into linear algebraic statements about $k^n$.
Nevertheless, I believe that this is the standard proof of the Bruhat decomposition, and explains why it is true: the relative position of two flags is described by an element of the Weyl group.