The R randomForest package includes functions for doing a rough imputation of missing values and then iterativelly improving this imputation based on case proximity in RF runs.
There are a bunch of other methods that have been proposed as ways rf's and decision trees can handle missing values:
1) Leave them out when split and do a bias correction for the reduction in impurity.
2) Split them onto a a third branch at each node.
3) Label them as a separate category as chf suggests. For numerical features impute and create a separate x_is_missing feature.
4) Identify "surrogate splitter" relationships between features by analyzing which features work well in the same place and then use a surrogate to split when a feature is missing.
5) Do a local imputation within the branch of the tree.
I'm not aware of R code for most of these though it may exist.
I implemented a stand alone utility that can do the first two methods:
It is easy enough to use write.arff to dump you're data out and call it and load the predictions (which are stored in a tsv) back in. (The arff file format is nice for categorical data with missing values).
I chose those two methods as they don't increase the computation required on large data sets. I've found the first works well when there are few missing values and they aren't meaningfully distributed...imputation often also works well here.
The second, three way splitting, works well when the fact a value is missing may be significant. This is quite common in poorly designed survey's that don't include a "don't know" or "not applicable" category. Method 3 can also work well here.