Undoubtedly, mobile devices (mainly smartphones and tablets up to now) have become the new paradigm of user-computer interaction. The use of such gadgets is increasing to unexpected figures and, at the same time, the number of potential security risks. This paper focuses on the bad-intentioned Android apps, as it is still the most widely used operating systems for such devices. Accurate detection of this malware remains an open challenge, mainly due to the ever-changing nature of malware and the “open” distribution channel of Android apps through Google Play. Present work uses feature selection for the identification of those features that may help in characterizing mobile Android-based malware. Maximum Relevance Minimum Redundancy and genetic algorithms guided by information correlation measures have been applied to the Android Malware Genome (Malgenome) dataset, attaining interesting results on the most informative features for the characterization of representative families of existing Android malware.