My planned setup is as follows:
Analog Fax machine -> Fritz!Box -> Asterisk -> Telephone network
My problem is, how do I convince the Fritz!Box to connect as a SIP client to my Asterisk instance?
Server Fault is a question and answer site for system and network administrators. It only takes a minute to sign up.
Sign up to join this communityThis should point you in the right direction:
http://www.asteriskguru.com/tutorials/fritz_box.html
(this was the first hit off google for "Fritz!Box asterisk")
From my experience with FritzBox and Asterisk servers it's most probably better, to let the FritzBox connect directly to the VOIP provider to send out faxes. I tried it to connect the FritzBox to the Asterisk server and then send out faxes, but the connection was quite unstable. I had more and better luck with letting the Fritzbox connect directly to the voip provider.
Sounds like you need one of these: http://www.voipsupply.com/voip-adapters/single-fxs
I'm not familiar with fritz!box, but one of those adapters will probably take care of getting your fax machine going with your asterisk box.