I've been using the $K$-fold cross-validation a few times now to evaluate performance of some learning algorithms, but I've always been puzzled as to how I should choose the value of $K$.

I've often seen and used a value of $K = 10$, but this seems totally arbitrary to me, and I now just use $10$ by habit instead of thinking it over. To me it seems that you're getting a better granularity as you improve the value of $K$, so ideally you should make your $K$ very large, but there is also a risk to be biased.

I'd like to know what the value of $K$ should depend on, and how I should be thinking about this when I evaluate my algorithm. Does it change something if I use the stratified version of the cross-validation or not?

The choice of $k = 10$ is somewhat arbitrary. Here's how I decide $k$:


first of all, in order to lower the variance of the CV result, you can and should repeat/iterate the CV with new random splits.  This makes the argument of high $k$ => more computation time largely irrelevant, as you anyways want to calculate many models. I tend to think mainly of the total number of models calculated (in analogy to bootstrapping). So I may decide for 100 x 10-fold CV or 200 x 5-fold CV.
@ogrisel already explained that usually large $k$ mean less (pessimistic) bias. (Some exceptions are known particularly for $k = n$, i.e. leave-one-out).
If possible, I use a $k$ that is a divisor of the sample size, or the size of the groups in the sample that should be stratified.
Too large $k$ mean that only a low number of sample combinations is possible, thus limiting the number of iterations that are different. 


For leave-one-out: $\binom{n}{1} = n = k$ different model/test sample combinations are possible. Iterations don't make sense at all.
E.g. $n = 20$ and $k = 10$: $\binom{n=20}{2} = 190 = 19 ⋅ k$ different model/test sample combinations exist. You may consider going through all possible combinations here as 19 iterations of $k$-fold CV or a total of 190 models is not very much. 

These thoughts have more weight with small sample sizes. With more samples available $k$ doesn't matter very much. The possible number of combinations soon becomes large enough so the (say) 100 iterations of 10-fold CV do not run a great risk of being duplicates. Also, more training samples usually means that you are at a flatter part of the learning curve, so the difference between the surrogate models and the "real" model trained on all $n$ samples becomes negligible. 

