Concrete can set underwater, it's a chemical reaction. Also, welding can be done underwater. There doesn't seem to be much rebar from 10,000 years ago, not that it rusted away, it just appears steel wasn't used much back then.
Portland Cement sets under water, the Romans invented it. Mortar and concrete are mixtures of Portland and aggregate.