Configure OSX Firewall to Allow SSH Server?

I've seen this too - It seems that the OSX Application Firewall is getting confused. I managed to get mine going by doing the following:

sudo rm /Library/Preferences/com.apple.alf.plist

Then reboot.

Once the machine comes back up, when you go to Firewall > Advanced Settings, you should only see the system services you have enabled (in your case, SSH and Screen Sharing). The rest of the entries will have gone, but when you start any applications that need access through the firewall, OSX will ask you to permit the application or not again and should then be added back to the firewall exceptions list (if you allow it incoming connections).

The commands below worked for me on Yosemite

cd /usr/libexec/ApplicationFirewall
sudo ./socketfilterfw --setloggingmode on
sudo ./socketfilterfw --setloggingopt detail
sudo tail -f /var/log/appfirewall.log

Try to connect to your Mac over SSH. You should see a deny entry, in my case sshd-keygen-wrapper

Oct 27 15:22:12 myhost socketfilterfw[4940] <Info>: Deny sshd-keygen-wrapper connecting from 192.168.0.2:49470 to port 22 proto=6

Then simply add /usr/libexec/sshd-keygen-wrapper (as suggested by mehaase) to the list of allowed applications, but there is no need to reboot

To switch the logging level back

./socketfilterfw --setloggingopt throttled

In my case, I added /usr/libexec/sshd-keygen-wrapper to the firewall settings and rebooted.

I found the idea here: https://discussions.apple.com/thread/2174585?threadID=2174585

One good troubleshooting technique: open Console.app and watch /var/log/appfirewall.log (or tail -f /var/log/appfirewall.log from the command line).