Does the average increase of a "re-roll" increase with the size of the dice? I'm having trouble modeling the following scenario:

Roll two dice and take the best
  result.

What is the proper way to model the average result from this? I understand intuitively that the average should go up, but I'm having trouble understanding exactly what plays into this increase.
Furthermore, is the increase greater or simply proportional in dice of larger size  (more sides)? For comparison's sake, consider a normal 6-sided die, and a 12-sided die.
 A: You have $n^2$ possible outcomes for two dice, where $n$ is the number of sides. The next step is to calculate the probability for each maximum pip ($k$).
For $k=1$ there is one possible outcome (1, 1). 
For $k=2$ there are three possible outcomes {(1,2), (2,1), (2,2)}
For $k=j$ there are $2j-1$ possible outcomes. Here's a small graphic to illustrate this relation.

Finally calculate the expected value: $\sum_{i=1}^{n} p(i)i = \sum_{i=1}^{n} \frac{2i-1}{n^2}i = \frac{(n+1)(4n-1)}{6n}$.
A: Alternatively, in the limit of large number of sides you can think of rolling a die as picking a uniformly distributed random number on $[0,1]$, and then multiplying by the number of sides. So you're trying to find $E(max(X,Y))$ where $X, Y$ are independent uniform[0, 1] random variables. This is
$$ \int_0^1 \int_0^1 \max(x,y) \: dx \: dy $$
which you can split according to whether $x$ or $y$ is larger, giving
$$ \int_0^1 \int_y^1 x \: dx \: dy + \int_0^1 \int_0^y y \: dx \: dy. $$
Both of these integrals are $1/3$ and so $E(\max(X,Y)) = 2/3$; this tells you that the larger of the two dice will be, on average, $2n/3$. Of course this agrees with Tim's answer. (It turns out that if you have $k$ dice each with $n$ sides, the expectation of the largest die would be about $kn/(k+1)$.)
If you don't know calculus, don't worry about this. If you do know calculus, I hope this helped.
A: A quick simulation in R indicates the increase is proportional to the number of sides of the dice
means = NULL
for(i in seq(6,72,by=6)) {
  dice1 = sample(1:i, 10000, replace=T)
  dice2 = sample(1:i, 10000, replace=T)
  m = mean(pmax(dice1, dice2))
  means = c(means, m)
}

plot(means)

