How to estimate a user's gender based on what apps the user download?
If you have data on how many downloads have been done for each category, you can use that data to perform logistic regression, where your target variable would be 0/1 classification of male/female. This will form your benchmark result and then you can improve upon the results. Especially look for feature selection, because there might be categories of apps which have nothing to do with target. You should also try bi variate profiling of variables with target to see if there is good correlation with target. 
Try using some advanced techniques once you have done some data exploration. 
KNN, Random Forest and Neural network for classification might give good results. Also cart might work fantastically here.