My question now is, how do I have to connect this Pins to the Arduino Mega.
Where do I have to connect the 74LS00N parts (which Pins) then the top left parts with the 10KOhm resistors and the part which is on Pin 5?
Unfortunately that sketch doesn't use a #defines section to assign pin
numbers to names, so without editing it you'll have to stick to the same
wiring.
The comment at the top does relate Arduino pin numbers to function though.
The diagram has a raw ATmega chip in there - you can relate Arduino pin numbers
to AVR pin names thus: