What does it mean to take the "average" of two decision trees by 'voting'
I think that you are mixing together two different things - random forests 
for regression and for classification. Regression means to predict a 
continuous value (number). Random forest can construct multiple regression 
trees, each of which makes a prediction about the number.  In that case, 
it is simple to understand. The numerical predictions are averaged to give 
a robust prediction of the true number value. 

However, I think that you are asking about classification - predicting a 
nominal value (also called categorical or factor). In this case, each 
decision tree predicts a category.  Usually, it does not make sense to 
talk about averaging categories. Instead, the multiple decision trees 
"vote" - that is one counts how many times each category was predicted 
and takes the category that received the most votes as the prediction. 
There is no averaging, only counting. 

Here is a simple example. 

Data

V1   V2    V3    Class
A     C     E      X
A     C     F      X
B     C     F      Y
B     D     F      Y 
B     D     E      X


Decision Tree 1 uses only feature V1:
If V1 = A, predict X, otherwise predict Y

Decision Tree 2 uses only feature V2:
If V2 = C, predict X, otherwise predict Y

Decision Tree 3 uses only feature V3:
If V3 = E, predict X, otherwise predict Y

Now we want to predict the class of a new point (A, C, F):
 - Decision Tree 1 sees V1 = A and predicts Class=X
 - Decision Tree 2 sees V2 = C and predicts Class=X
 - Decision Tree 3 sees V3 = F and predicts Class=Y
There were two votes for X and one vote for Y,  so the forest predicts X, 
the class that received the  majority of the votes.