What determines the topology/connectedness of quantum computers?

What limits the connectedness is ultimately a platform-specific question. For example, in trapped-ion quantum computers, all of the ions are coupled through a collective motional mode such that all qubits are actually "connected", so that the graph of qubit-qubit connections is complete.

The more mainstream approach (at least in industry) involves the use of superconducting qubits, which encompasses an ever-growing zoo of different qubit models (transmons, fluxonium, etc.), each with its pros and cons. Since these designs are fabricated via lithographic processes onto 2-dimensional substrates, the geometry of the plane itself constrains which qubits can talk to each other. The difficulty lies in the fact that on top of these couplings, the qubits also require drive and readout lines that need to reach the edge of the chip so that the signals can be routed through the qubit chip housing and eventually to classical control hardware. There are ways of getting "lines" (coplanar waveguides) to cross on chips via airbridges, and there is current work on 3D-integrated technology that can "break the plane", where different aspects of the chip's functionality are spread across different wafers that can be stacked and bonded in the vertical direction.

Furthermore, like you said, decoherence is also generally an issue, because for certain qubit types, having too many couplings can cause frequency crowding. More specifically, when two-qubit gates (like CNOTs) are implemented, specific resonances between coupled qubits are driven by precisely timed and shaped signals. When there are many couplings, there are many potential resonances that could be driven, when only one is actually desired for the gate. Thus, it becomes increasingly difficult to isolate the desired one (the signal might have a limit on its spectral purity), and these spurious resonances (cross-talk) will result in erroneous entanglement.