What you are vaguely describing PB is the method used for a gravity rig. This purely uses its own weight to sit it on the sea floor.
Bridge piers and other permanent structures are usually built within caissons. These are temporary coffer dams where the water is pumped out from inside. Obviously in deep water this is impractical, so piles are driven or drilled into the bedrock from drilling barges. A structure can then be built up on this network of piles.
There are several other methods available to over come the problem; you just have to use the one most suitable.
Forgot to say, caissons are sometimes pressurised to keep the water out, so the muck/rock can be dug out. Early navvies who worked in these often came down with the 'bends' (as the problems of nitrogen bubbles forming in the blood weren't really understood). As no one knew why this was happening, it came to be known as 'caisson sickness'. The first pressurised caisson in the world was used by IKB to build the centre pier foundation for the Royal Albert bridge at Saltash.