Make your predictions using a single model trained on the entire dataset (so there is only one set of features). The cross-validation is only used to estimate the predictive performance of the single model trained on the whole dataset. It is VITAL in using cross-validation that in each fold you repeat the entire procedure used to fit the primary model, as otherwise you can end up with a substantial optimistic bias in performance.
To see why this happens, consider a binary classification problem with 1000 binary features but only 100 cases, where the cases and features are all purely random, so there is no statistical relationship between the features and the cases whatsoever. If we train a primary model on the full dataset, we can always achieve zero error on the training set as there are more features than cases. We can even find a subset of "informative" features (that happen to be correlated by chance). If we then perform cross-validation using only those features, we will get an estimate of performance that is better than random guessing. The reason is that in each fold of the cross-validation procedure there is some information about the held-out cases used for testing as the features were chosen because they were good for predicting, all of them, including those held out. Of course the true error rate will be 0.5.
If we adopt the proper procedure, and perform feature selection in each fold, there is no longer any information about the held out cases in the choice of features used in that fold. If you use the proper procedure, in this case, you will get an error rate of about 0.5 (although it will vary a bit for different realisations of the dataset).
Good papers to read are:
Christophe Ambroise, Geoffrey J. McLachlan, "Selection bias in gene extraction on the basis of microarray gene-expression data", PNAS http://www.pnas.org/content/99/10/6562.abstract
which is highly relevant to the OP and
Gavin C. Cawley, Nicola L. C. Talbot, "On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation", JMLR 11(Jul):2079−2107, 2010 http://jmlr.csail.mit.edu/papers/v11/cawley10a.html
which demonstrates that the same thing can easily ocurr in model selection (e.g. tuning the hyper-parameters of an SVM, which also need to be repeated in each iteration of the CV procedure).
I would recommend using Bagging, and using the out-of-bag error for estimating performance. You will get a committee model using many features, but that is actually a good thing. If you only use a single model, it will be likely that you will over-fit the feature selection criterion, and end up with a model that gives poorer predictions than a model that uses a larger number of features.
Alan Millers book on subset selection in regression (Chapman and Hall monographs on statistics and applied probability, volume 95) gives the good bit of advice (page 221) that if predictive performance is the most important thing, then don't do any feature selection, just use ridge regression instead. And that is in a book on subset selection!!! ;o)