Brain gender differences have been known for a long time and are the possible reason for many psychological, psychiatric and behavioral differences between males and females. Predicting genders from brain functional connectivity (FC) can build the relationship between brain activities and gender, and extracting important gender related FC features from the prediction model offers a way to investigate the brain gender difference. Current predictive models applied to gender prediction demonstrate good accuracies, but usually extract individual functional connections instead of connectivity patterns in the whole connectivity matrix as features. In addition, current models often omit the effect of the input brain FC scale on prediction and cannot give any model uncertainty information. Hence, in this study we propose to predict gender from multiple scales of brain FC with deep learning, which can extract full FC patterns as features. We further develop the understanding of the feature extraction mechanism in deep neural network (DNN) and propose a DNN feature ranking method to extract the highly important features based on their contributions to the prediction. Moreover, we apply Bayesian deep learning to the brain FC gender prediction, which as a probabilistic model can not only make accurate predictions but also generate model uncertainty for each prediction. Experiments were done on the high-quality Human Connectome Project S1200 release dataset comprising the resting state functional MRI data of 1003 healthy adults. First, DNN reaches 83.0%, 87.6%, 92.0%, 93.5% and 94.1% accuracies respectively with the FC input derived from 25, 50, 100, 200, 300 independent component analysis (ICA) components. DNN outperforms the conventional machine learning methods on the 25-ICA-component scale FC, but the linear machine learning method catches up as the number of ICA components increases...