Antes del onreadystatechange=function() debería estar el innerHTML que contiene el GIF y despues de todo va el responseText, mira este ejemplo:
  
Código:
 	document.getElementById('div').innerHTML = '<img src="images/sending.gif">';
	ajax.open("POST", "web.php",true);
	ajax.onreadystatechange=function(){
		if (ajax.readyState==4) {
			c.innerHTML = ajax.responseText
		}
	}