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.
This 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.