In Guns, Germs and Steel, how does a society that becomes mainly agricultural change in terms of its political structure?
The answer to your question can be found in Chapter Four, entitled "Farmer Power." In this chapter, Diamond discusses how the move from being a society that is based on hunting and gathering to a mainly agricultural society also resulted in the political development of that society. This is mainly due to the way that the move also involves a huge population boost, which then enables the development of specialists:
A separate consequence of a settled existence is that it permits one to store food surpluses, since storage would be pointless if one didn't remain nearby to guard the stored food... Two types of such specialists are kings and bureaucrats... when food can be stockpiled, a political elite can gain control of food produced by others, assert the right of taxation, escape the need to feed itself, and and engage in full-time political activities.
This is why the agricultural societies that Diamond explores are often arranged into political units that have a greater population and a higher level of organisation which enables them to mobilise armed forces and invade other territories. Hunter-gathering is thus shown to be a profound limitation in early societies. Those that got ahead of the starting line were those that quickly developed into agricultural societies before their neighbours.