Since Paradigm Shifter has given away the main idea, this is how I would do it.

We'll build the basis B incrementally, thusly:

Initialize B = {v}.
while (the span of B is not the whole space) {
  Let w be a vector that is not in the span of B.
  Find the orthogonal projection of w into the span of B, u. The vector w-u is now perpendicular to the span of B, so it is orthogonal to all the vectors in B. Add w-u to B
}

This program will stop after n-1 steps if we are doing this in R^n. At the end, B will be an orthogonal basis that contains v.

If you know about Gram-Schmidt diagonalization, you can do it with a shorter description, like this:

Initialize B = {v}.
while (the span of B is not the whole space) {
  Let w be a vector that is not in the span of B.
  Add w to B.
}
Use the Gram-Schmidt procedure to turn B into an orthogonal basis whose first vector is v.

EDIT: With a little bit of work I am sure one can generalize the theorem to any inner product space, even if ones with infinite dimension.