Sendmail includes a facility for plugging in custom mail filters, called milters. It's documented here. Graymilter uses this facility to implement graylisting. This is an idea invented by Evan Harris in 2003. Basically, the first time someone tries to send you mail, you send back a temporary failure response. A real email system will put the mail into a queue and re-try it later, at which time the address will have graduated from the graylist to the whitelist, so the mail will get through. However, spam engines and worms do not have real email systems. They are optimized for sending out mass quantities of mail, and they generally do not implement re-trying. Therefore mail from those sources will not get through.
The advantages of graylisting are that it's very simple, it requires zero maintenance, and it will never block any real mail. The disadvantage is that it delays mail. However, people you correspond with every day will stay in the whitelist and will get through immediately. For other folks, well, the delay is brief.
In Evan's original concept, a listing would consist of three data items: the source IP address, the envelope sender address, and the envelope recipient address. Graymilter implements a simplified version of the idea, using only the source IP address. These can be stored much more efficiently, so graymilter can be used on sites with very high traffic.
This is very abbreviated, intended mainly as a reminder for those who have worked with milters before. If it's your first milter, you should look on the web for more thorough documentation. Also, these instructions are pretty specific to FreeBSD, and will have to be adapted for other OSs.
If you don't see MILTER in the compilation options, you will have to re-build sendmail.sendmail -d0.1 -bt < /dev/null | grep MILTER
Rebuild and install sendmail.cf.INPUT_MAIL_FILTER(`graymilter',`S=unix:/var/run/graymilter.sock, T=S:4m;R:4m')
# graymilter unix:/var/run/graymilter.sock
graymilter_enable="YES" graymilter_flags="" graymilter_socket="unix:/var/run/graymilter.sock"