We don't know
No writings I've been able to find discuss the construction of the bridge in any level of detail. Any of the possibilities discussed in the question comments are feasible:
- As proposed by amaranth, they could have dug out the cavern around the bridge, potentially uncovering a larger, natural cavern below1
- As proposed by HorusKol and maguirenumber6, it may actually be built out of stone blocks, but the seams are either hidden by Dwarf-craft or too faint for us to see
- As proposed in the question itself, it could have been a natural "bridge", merely shaped by the Dwarves into the shape they wanted
However, I would question the claim that the Dwarves couldn't have constructed a bridge that looked like (and was as strong as) a single, unbroken piece of stone. Such a technique is used to hide their doors, including the West-gate of Moria itself:
[W]here are the Doors? I can't see any sign of them.'
'Dwarf-doors are not made to be seen when shut,' said Gimli. `They are invisible, and their own masters cannot find them or open them, if their secret is forgotten.'
[S]ilently a great doorway was outlined, though not a crack or joint had been visible before.
Fellowship of the Ring Book II Chapter 4: "A Journey in the Dark"
Or the back-door of Erebor:
It was not a cave and was open to the sky above; but at its inner end a flat wall rose up that in the lower part, close to the ground, was as smooth and upright as mason's work, but without a joint or crevice to be seen. No sign was there of post or lintel or threshold, nor any sign of bar or bolt or key-hole; yet they did not doubt that they had found the door at last.
The Hobbit Chapter 11: "On the Doorstep"
It's worth remembering that Dwarves are preternaturally skilled miners, carvers, and stone-workers; techniques that seem impossible to us are not necessarily beyond their abilities.
1 It's doubtful, though not impossible, that they carved the whole thing, since Gimli says that none know how deep it goes, and Gandalf discusses tunnels at that depth not made by Dwarvish hands:
'Deep is the abyss that is spanned by Durin's Bridge, and none has measured it,' said Gimli.
'We fought far under the living earth, where time is not counted. Ever he clutched me, and ever I hewed him, till at last he fled into dark tunnels. They were not made by Durin's folk, Gimli son of Glóin. Far, far below the deepest delving of the Dwarves, the world is gnawed by nameless things.
The Two Towers Book III Chapter 5: "The White Rider"