There are quite a few different autonegotiation standards. The earlier standards (pre 802.3ab in 1999) were less than reliable, so you would have some cases where negotiation was done incorrectly between a host port and a switch port when both were doing negotiation.
The negotiation standards work by sending pulses, called FLP pulses, across the link. These pulses are 16 bits in most (all?) standards. The important bits are 0 through 12, 13, and 16. 0 through 12 defines the standards used and capabilities of the link. 13 defines a link failure and 16 defines an acknowledgement.
Most NICs won't send or pay attention to an FLP if autonegotiation is disabled in the NIC software. It is possible the port will come up in half duplex, depending on the switch (many early-generation 100Mbits switches were this way). On Gigabit capable ports, the port should default to full duplex, but this depends on how the manufacturer implemented the standard.
However, you didn't state whether or not your host was connected to a port capable of 100 Mbps operation. Not all Gigabit ports are (e.g., in a 1Gb/10Gb switch). If the port is connected to a switch which does not advertise the correct modes supported by your card, the port will not connect.
Here's an excellent reprint from PowerSolutions that describes the process in detail -- and this is a great presentation on autonegotiation from the IOL at University of New Hampshire which is an exceptional treatment of the subject.