Asterisk fax

In short:

Across the Internet even a G.711 codec fax transmission is unpredictable. An excellent discussion of why faxing and modems don't work well over VoIP can be found here. However, people often get perfectly good results on lightly loaded LANs. It still isn't perfect, as a burst of data on the LAN can still upset things, but some people get results they can live with.

Fax-over-Internet T.38 pass-thru functionality within Asterisk has arrived in 1.4, CallWeaver has reliable support for both T38 passthrough and T38 termination; CallWeaver is a fork of Asterisk 1.2. You should also consider Hylafax+ (or HylaFax) which runs outside of Asterisk but can be bridged using IAXModem to Asterisk; this is a robust solution when receving calls via PRI and forwarding to iaxmodem and hylafax on localhost. Details are explained at the SpanDSP web site.
A commercial alternative is Noojee Fax (aka AsterFax) which allows you to use Asterisk to send and recieve faxes normally then converts them to an email message or the other way around (email-to-fax). Another alternative is the web-based fax server from VBS.

In detail:
There are two conceptual methods of carrying virtually real-time fax-machine-to-fax-machine communication across packet networks:

Fax relay, in which the T.30 fax from the PSTN is demodulated at the sending gateway. The demodulated fax content is enveloped into packets, sent over the network, and remodulated into T.30 fax at the receiving end.
Fax pass-through, in which modulated fax information from the PSTN is passed in-band end-to-end over a voice speech path in an IP network. The following two pass-through techniques are possible:
The configured voice codec is used for the fax transmission. This technique works only when the configured codec is G.711 with no voice activity detection (VAD) and no echo cancellation (EC), or when the configured codec is a clear-channel codec or G.726/32. Low bit-rate codecs cannot be used for fax transmissions.
The gateway dynamically changes the codec from the codec configured for voice to G.711 with no VAD and no EC for the duration of the fax session. This method is specifically referred to as codec upspeed or fax pass-through with upspeed.
In addition to the methods for real-time fax transmission, a method called store-and-forward fax breaks the fax process into distinct sending and receiving processes and allows fax messages to be stored between those processes. store-and-forward fax is based on the ITU-T T.37 standard, and it also enables fax transmissions to be received from or delivered to computers rather than fax machines.

Yet another Fax-over-IP method is to use IAXmodem and Hylafax on different, distanced machines: You could run IAXmodem on the Asterisk server communicating on the loopback adapter, and HylaFAX would communicate with IAXmodem remotely using a "remote tty" service such as termpkg's termnetd and ttyd programs.

The Noojee Fax (aka AsterFax) method applies a bit of lateral thinking. It allows you to use an Asterisk server which is connected to the PSTN to act as a fax gateway to the IP network. Noojee Fax sits on the Asterisk server and operates as a translater converting the faxes to and from email messages. The fax is then sent over the IP network as an email message which eliminates all the standard problems of Fax-over-IP.
User then can send a fax from their favorite email client and receive it into their in-box. While perhaps not suitable for all usage scenarios this method covers a good percentage of the common use cases and completly eliminates the vagaries of Fax-over-IP.

T.38 relay:
In fax relay mode, gateways terminate T.30 fax signaling by spoofing a virtual fax machine to the locally attached fax machine. Unlike in-band faxing or fax pass-through, fax relay breaks down the T.30 fax tones into their specific HDLC frames (demodulation), sends the information across the voice network using the fax relay protocol (T.38), and then converts the bits back into tones at the far side (modulation). The fax machines on either end are sending and receiving tones and are not aware that a demodulation/modulation fax relay process is occurring.

Summary:
Fax pass-through is the simplest technique for sending fax over IP networks, but it is not the default, nor is it the most desirable method of supporting fax over IP. T.38 fax relay provides a more reliable and error-free method of sending faxes over an IP network

Can I fax over a call with GSM codec compression? What about G.729? Other complex codecs?

Note: G.726 is the only lowish bit rate in common use that can handle FAX at all. It is, however, limited to 9600bps. The V.17 rates higher than 9600bps (14,400 and 12,000), and 33,600bps V.34 FAXing will not work. Even 9600bps FAX performance suffers in reliability, as it will only function if the signal coming in from the analogue sections of the call path is clean.