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 first one line, than the sum of that one with a second, then the sum of those two
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.