I had the same problem as you did and after a few hours of "research", I am finally able to figure it out. Check out my brand new, not yet public forum at: fitnesssocial.com
The mod developer did not explicitly tell us that you need to review at least two installation files: follow my steps below will save you some time
Step2: open install.xml in your browser and do everything it asks you to - I believe you have done setting up database with user_gender and updating all the files to your website, you are half way done, but not yet.
Step3: depends on which style you use, you must follow the mod installation for that style - it's located under \templates, prosilver.xml and subsilver.xml: use browser to open the one that is suitable for you.
Step4: follow the installation instruction - note that you must copy those gender icon images to your websites.
Step5: after you are done, do not forget to log into your admin control panel and click on "style" tab, you must refresh both template and imageset to have the gender selection shown.
Finally, log into your profile editing page and enjoy!
I know, it's really confusing, espeically for us first timer. The logic is not hard, it's just sometime we rely too much on instruction that we doubt common sense.