Si miras la documentacion de NMAP, verás la descripción de como lo hacen:
http://nmap.org/book/osdetect.html
y de hecho el código de NMAP es abierto, así que hasta lo podrías mirar.
Como se trata de enviar paquetes TCP y UDP y observar las respuestas, tendrías que mirarte, como mínimo, el tema de sockets en Java.
S!