How to define person's gender from the fullname?
That dataset looks like a good starting point. Keep in mind that when you make your own dataset from those datasets you'll want to keep the male to female ratio balanced if you want it to predict both well. 

It should not matter what machine learning software you use (Apache Mahout, scikit-learn, weka, etc.). Pick one that fits your language of choice since speed will probably not be too much of a concern with the smallish dataset size. As for features, you'd generally use ngrams as your baseline for NLP classification tasks. If you use ngrams here you won't end up with anything very interesting because the model won't generalize to any unseen names. I'd suggest as a feature baseline that you try character ngrams, and maybe something like syllable ngrams for something slightly more advanced (for syllable tokenization see https://stackoverflow.com/questions/405161/detecting-syllables-in-a-word).