I'll answer in two ways. First of all, what is wrong with them agreeing which axis to measure? As the comments above state, even classical bits (such as a lamp being on or off) require some prior agreement in order to allow interpretation of the signal. You state that a qubit requires extra agreement. But does it really? Suppose they agree to measure along the up/down axis defined by gravity, or the axis that points towards the north star. This is much less agreement than has been done ahead of time in order for cell phones to agree how to interpret the signals that are sent to them, so you could just as well ask how is it that radio waves can convey information if so much prior agreement is needed.
In general, one assumes that the communicating parties can do as much prior work as needed in order to construct their protocol. Otherwise, even if Alice can send Bob a "1", how would he know that is supposed to mean he should pick up a gallon of milk on his way home from work?
The second point is that there are ways for the qubits themselves to convey the information about which axis should be measured. For example, if Alice wanted to send a million bits of information she could first send a thousand qubits that all spin in the same direction. Bob can do tomography on these to deduce the proper axis. Basically, he measures many possible axes to determine which one consistently gives the same measurement result. Having determined the axis using these calibration qubits, he can then decode the data from the rest.